<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>

class Solution:
    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
        """Solution 2:"""
        # build the initial graph, without replacing any -1s
        graph = self.build_graph(edges, 0)
        # get the shortest distance from source to destination without replacing any -1s
        unmodified_distance = self.dijkstra(n, graph, source, destination)
        # if this shortest distance is less than target, then the task is impossible, because
        # replacing any -1s will only make the shortest distance even smaller
        if unmodified_distance < target:
            return []
        # if this shortest distance equals target, then just trivially replace any -1s with the
        # largest possible value, since this largest possible value is strictly larger than
        # n * edge_weight >= target, and so this modification will not affect the existing shortest
        # path that already equals target
        if unmodified_distance == target:
            res = []
            for u, v, c in edges:
                cost = c
                if cost == -1:
                    cost = 2 * (10 ** 9)
                res.append([u, v, cost])
            return res
        
        # now we know that unmodified_distance > target
        # the key idea is that if we replace all the -1s with the minimum possible edge weight (which
        # is 1) then either we have shortest_path <= target (in which case the task is possible) or
        # shortest_path > target (in which case the task is impossible)
        # in the latter case we can just return an empty array
        # so the only interesting case is the former case
        # since the task is possible, all we need to be able to do is just identify which edge (that
        # was originally -1) was actually part of the shortest path. then we can just set its value
        # to be 1 + target - shortest_path.
        # indeed, this is because there
        # could be some edges (that were originally -1) that are not in the shortest path, and so
        # modiyfing them to target - shortest_path will not change the total distance required
        # to do so, we can iterate sequentially over the edges and one-by-one change them from
        # -1 to 1. as soon as we find an edge such that we go from shortest_path > target to
        # shortest_path <= target, we have found such an edge. this is what Solution 2 does.
        # Solution 1 just realizes that this is equivalent to finding the smallest number of edges
        # that we flip from -1 to 1 required to ensure that shortest_path <= target, and we can just
        # binary search this. the monotonicity property here is just that flipping an edge from -1
        # to 1 can only reduce the shortest path, and so flipping more edges will only further
        # reduce the shortest path
        # note that showing the following property is important: let E be the first edge
        # flipped which ensures we go from old_shortest_path > target to shortest_path <= target
        # then when we set E to have weight 1 + target - old_shortest_path, the shortest distance between
        # source and destination is indeed target
        # this is very intuitive, but worth arguing formally. to see this, just note that after this
        # assignment the shortest distance is of course at most target, since we can take the same path
        # as when the edge weight was 1, but it now has an additional target - old_shortest_path
        # and so the total path cost is target. call this path P1. but could there be an even faster
        # path? well, such a path P2 must go through E (otherwise we have a path faster than target
        # that does not use E which is a contradiction). and if it goes through E, then since E
        # connects some vertex u to some vertex v, we know that both P1 and P2 follow the path of
        # source -> u -> v -> destination. so where in this path does P2 become faster than P1?
        # well, P2 cannot be faster in going source -> u, because this portion does not use E and so
        # P1 also could avail this option. similarly, P2 cannot be faster in going v -> destination
        # because again this portion does not use E and so P1 also could avail this option. hence
        # we must have that cost(P1) == cost(P2).
        total_negatives = 0
        for _, _, c in edges:
            total_negatives += 1 * (c == -1)
        return self.solution_2(total_negatives, n, edges, source, destination, target)

    def solution_1(self, total_negatives, n, edges, source, destination, target):
        left, right = 1, total_negatives
        while left < right - 1:
            mid = (left + right) // 2
            graph = self.build_graph(edges, mid)
            cost = self.dijkstra(n, graph, source, destination)
            if cost <= target:
                right = mid
            else:
                left = mid + 1
        graph = self.build_graph(edges, left)
        cost = self.dijkstra(n, graph, source, destination)
        if cost <= target:
            return self.process_edges(left, edges, 1 + target - cost)
        graph = self.build_graph(edges, right)
        cost = self.dijkstra(n, graph, source, destination)
        if cost <= target:
            return self.process_edges(right, edges, 1 + target - cost)
        return []


    def solution_2(self, total_negatives, n, edges, source, destination, target):
        for num_negative_to_replace in range(1, total_negatives + 1):
            graph = self.build_graph(edges, num_negative_to_replace)
            cost = self.dijkstra(n, graph, source, destination)
            if cost <= target:
                return self.process_edges(num_negative_to_replace, edges, 1 + target - cost)
        return []
    
    def process_edges(self, num_negative_to_replace, edges, imputation):
        res_edges = []
        num_negative_replaced = 0
        for u, v, c in edges:
            cost = c
            if c == -1:
                if num_negative_replaced == num_negative_to_replace - 1:
                    cost = imputation
                elif num_negative_replaced < num_negative_to_replace - 1:
                    cost = 1
                # don't forget to set all the other -1s to a large value so they don't affect the
                # shortest path computation
                else:
                    cost = 2 * (10 ** 9)
                num_negative_replaced += 1
                
            res_edges.append([u, v, cost])
        return res_edges

    def build_graph(self, edges, num_negative_to_replace):
        graph = collections.defaultdict(list)
        num_negative_replaced = 0
        for u, v, c in edges:
            cost = c
            if c == -1:
                if num_negative_replaced == num_negative_to_replace:
                    continue
                num_negative_replaced += 1
                cost = 1
            graph[u].append((v, cost))
            graph[v].append((u, cost))
        return graph

    def dijkstra(self, n, graph, source, destination):
        heap_arr = [(0, source)]
        min_distances = [float('inf')] * n
        min_distances[source] = 0
        while heap_arr:
            total, curr = heapq.heappop(heap_arr)
            if curr == destination:
                return total
            for v, cost in graph[curr]:
                if total + cost < min_distances[v]:
                    min_distances[v] = total + cost
                    heapq.heappush(heap_arr, (total + cost, v))
        return float('inf')
6158