<p>You are given an <strong>undirected weighted</strong> <strong>connected</strong> graph containing <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>, and an integer array <code>edges</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>, w<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> with weight <code>w<sub>i</sub></code>.</p>

<p>Some edges have a weight of <code>-1</code> (<code>w<sub>i</sub> = -1</code>), while others have a <strong>positive</strong> weight (<code>w<sub>i</sub> &gt; 0</code>).</p>

<p>Your task is to modify <strong>all edges</strong> with a weight of <code>-1</code> by assigning them <strong>positive integer values </strong>in the range <code>[1, 2 * 10<sup>9</sup>]</code> so that the <strong>shortest distance</strong> between the nodes <code>source</code> and <code>destination</code> becomes equal to an integer <code>target</code>. If there are <strong>multiple</strong> <strong>modifications</strong> that make the shortest distance between <code>source</code> and <code>destination</code> equal to <code>target</code>, any of them will be considered correct.</p>

<p>Return <em>an array containing all edges (even unmodified ones) in any order if it is possible to make the shortest distance from </em><code>source</code><em> to </em><code>destination</code><em> equal to </em><code>target</code><em>, or an <strong>empty array</strong> if it&#39;s impossible.</em></p>

<p><strong>Note:</strong> You are not allowed to modify the weights of edges with initial positive weights.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/18/graph.png" style="width: 300px; height: 300px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
<strong>Output:</strong> [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
<strong>Explanation:</strong> The graph above shows a possible modification to the edges, making the distance from 0 to 1 equal to 5.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/18/graph-2.png" style="width: 300px; height: 300px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
<strong>Output:</strong> []
<strong>Explanation:</strong> The graph above contains the initial edges. It is not possible to make the distance from 0 to 2 equal to 6 by modifying the edge with weight -1. So, an empty array is returned.
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/19/graph-3.png" style="width: 300px; height: 300px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6
<strong>Output:</strong> [[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
<strong>Explanation:</strong> The graph above shows a modified graph having the shortest distance from 0 to 2 as 6.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code><font face="monospace">1 &lt;= edges.length &lt;= n * (n - 1) / 2</font></code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i&nbsp;</sub>&lt;&nbsp;n</code></li>
	<li><code><font face="monospace">w<sub>i</sub>&nbsp;= -1&nbsp;</font></code>or <code><font face="monospace">1 &lt;= w<sub>i&nbsp;</sub>&lt;= 10<sup><span style="font-size: 10.8333px;">7</span></sup></font></code></li>
	<li><code>a<sub>i&nbsp;</sub>!=&nbsp;b<sub>i</sub></code></li>
	<li><code>0 &lt;= source, destination &lt; n</code></li>
	<li><code>source != destination</code></li>
	<li><code><font face="monospace">1 &lt;= target &lt;= 10<sup>9</sup></font></code></li>
	<li>The graph is connected, and there are no self-loops or repeated edges</li>
</ul>

from typing import List
from collections import defaultdict
import heapq
import random

INF = int(1e9 + 1000)
M = int(1e9)


class Solution:
    def other_dijkstra(self):
        d = [INF for _ in range(self.n)]
        used = [False for _ in range(self.n)]

        d[self.source] = 0

        for _ in range(self.n):
            v = None

            for j in range(self.n):
                if not used[j] and (v is None or d[j] < d[v]):
                    v = j

            if d[v] == INF:
                break
            used[v] = True

            for to in self.graph[v]:
                d[to] = min(d[to], d[v] + self.get_cost(v, to))
        self.d = d
        return d[self.destination]

    def dijkstra(self):
        return self.other_dijkstra()

        d = [INF for _ in range(self.n)]
        queue = [(0, self.source)]

        used = [False for _ in range(self.n)]

        while queue:
            # print(d, used, queue)
            cost, v = heapq.heappop(queue)
            if used[v]:
                continue

            d[v] = cost
            used[v] = True

            for u in self.graph[v]:
                w = self.get_cost(v, u)
                if d[u] > d[v] + w:
                    d[u] = d[v] + w
                    heapq.heappush(queue, (w + cost, u))
        self.d = d
        return d[self.destination]

    def get_cost(self, v, u):
        if v > u:
            v, u = u, v

        return self.edges[v][u]

    def set_cost(self, v, u, w):
        if v > u:
            v, u = u, v

        self.edges[v][u] = w

    def get_lower_bound(self, v, u):
        """ Find edge value so that value + 1 does not affect answer """

        l, r = 1, M

        r_ans = INF
        while l + 5 < r:
            m = (l + r) // 2

            self.set_cost(v, u, m)
            m_ans = self.dijkstra()
            if m_ans > self.target:
                r = m
                continue

            self.set_cost(v, u, r)
            r_ans = self.dijkstra()

            if r_ans == m_ans:
                r = m
            else:
                l = m

        last_good = l
        # if v == 4 and u == 1:
            # print(self.get_edges())
            # print(l, r + 1)
            # print(self.dijkstra())
        for i in range(l, r + 1):
            self.set_cost(v, u, i)
            i_ans = self.dijkstra()

            # if v == 4 and u == 1:
                # print('inside for')
                # print(self.get_edges())
                # print(l, r + 1)
                # print(self.dijkstra())

            if i_ans < r_ans and i_ans <= self.target:
                last_good = i
            else:
                break
        return last_good

    def get_edges(self):
        ans = []
        for [a, b, w] in self.init_edges:
            if w == -1:
                ans.append([a, b, self.get_cost(a, b)])
            else:
                ans.append([a, b, w])

        return ans

    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int,
                           destination: int, target: int) -> List[List[int]]:
        self.n = n
        random.shuffle(edges)
        self.init_edges = edges
        self.edges = [[0 for _ in range(n)] for _ in range(n)]
        self.graph = defaultdict(list)
        self.source = source
        self.destination = destination
        self.target = target
        self.d = [INF for _ in range(n)]

        for [a, b, w] in edges:
            self.graph[a].append(b)
            self.graph[b].append(a)
            self.set_cost(a, b, w)

            if w == -1:
                self.set_cost(a, b, M)

        d = self.dijkstra()
        if d < target:
            return []

        for [a, b, w] in edges:
            if w == -1:
                self.set_cost(a, b, 1)

        d = self.dijkstra()
        if d > target:
            return []

        # print(self.get_edges())
        # for [a, b, w] in edges:
        #     if w != -1:
        #         continue
        #
        #     w = self.get_lower_bound(a, b)
        #     self.set_cost(a, b, w)

        # print(self.get_edges())

        for [a, b, w] in edges:
            if w == -1:
                self.set_cost(a, b, M)

        for [a, b, w] in edges:
            if w != -1:
                continue

            self.set_cost(a, b, 1)
            res = self.dijkstra()
            if res == self.target:
                return self.get_edges()

            if self.d[a] > self.d[b]:
                a, b = b, a

            # if res < self.target:
            last = self.d[self.destination] - self.d[b]
            nw = self.target - self.d[a] - last
            # print(self.d[self.destination], self.d[b], last, self.d[a], nw)
            self.set_cost(a, b, max(1, nw))
            # else:
            #     self.set_cost(a, b, 1)

        print(self.get_edges())
        if self.dijkstra() == self.target:
            return self.get_edges()
        return []


# print(Solution().modifiedGraphEdges( n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5))
# print(Solution().modifiedGraphEdges(n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6))
print(Solution().modifiedGraphEdges(n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6))
# print(Solution().modifiedGraphEdges(n = 5, edges = [[3,0,1],[2,1,-1],[2,3,6],[4,2,6],[1,3,2],[2,0,7],[0,4,10],[0,1,6]], source = 1, destination = 4, target = 14))
4797