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

    class DijkstraOptimized:
        def __init__(self, edges, num_nodes, start, target):
            from collections import defaultdict, deque
            self.graph = defaultdict(dict)
            self.num_nodes = num_nodes
            self.start = start
            self.target = target
            self.distances = {}
            self.predecessors = {}
            self.cache = {}
            self.update_queue = deque()
            
            # Initialize the graph with edges
            for u, v, weight in edges:
                self.graph[u][v] = weight
                self.graph[v][u] = weight
            
            # Initial run of Dijkstra's algorithm
            self.run_dijkstra()
        
        def run_dijkstra(self):
            import heapq
            distances = {i: float('inf') for i in range(self.num_nodes)}
            distances[self.start] = 0
            predecessors = {i: None for i in range(self.num_nodes)}
            priority_queue = [(0, self.start)]
            
            while priority_queue:
                current_distance, u = heapq.heappop(priority_queue)
                
                if current_distance > distances[u]:
                    continue
                
                for v, weight in self.graph[u].items():
                    distance = current_distance + weight
                    if distance < distances[v]:
                        distances[v] = distance
                        predecessors[v] = u
                        heapq.heappush(priority_queue, (distance, v))
            
            self.distances = distances
            self.predecessors = predecessors
            self.cache[(self.start, self.target)] = (self.distances[self.target], self.get_path(self.target))
        
        def update_edge(self, u, v, new_weight):
            # Update edge in the graph
            self.graph[u][v] = new_weight
            self.graph[v][u] = new_weight
            
            # Flag that an update has occurred
            self.update_queue.append((u, v))
            
            # Recompute the shortest paths after each update
            self.run_dijkstra()
        
        def get_path(self, target):
            path = []
            step = target
            while step is not None:
                path.append(step)
                step = self.predecessors[step]
            path.reverse()
            return path
        
        def query_shortest_path(self):
            # Return cached result if available
            if (self.start, self.target) in self.cache:
                return self.cache[(self.start, self.target)]
            
            # Otherwise compute and cache result
            self.run_dijkstra()
            return self.cache[(self.start, self.target)]


####

    def cleanEdgesFromZeros(self, edges):
        for t in edges:
            if t[2] == 0:
                edges.remove(t)
                edges.add((t[0], t[1], int(1e7)))

    def helperFunction(self, n, edges_set, source, destination, target, bfm):
        while True:
            shortest_distance, shortest_path = bfm.query_shortest_path()
            if shortest_distance > target:
                return []
            if shortest_distance == target:
                self.cleanEdgesFromZeros(edges_set)
                return edges_set

            
            shortestPathLengthRange = range(len(shortest_path)-1)

            nofzeros = sum(1 if (shortest_path[i], shortest_path[i+1], 0) in edges_set or (shortest_path[i+1], shortest_path[i], 0) in edges_set else 0 for i in range(len(shortest_path)-1))
            
            if nofzeros == 0: # We have no knobs, what can we do other than returning??
                if shortest_distance == target:
                    self.cleanEdgesFromZeros(edges_set)
                    return edges_set
                else:
                    return []
            
            diff = target - shortest_distance
            new_value = 1

            if diff > nofzeros:
                if nofzeros > 0:
                    new_value += diff - nofzeros

            for i in shortestPathLengthRange:
                if (shortest_path[i], shortest_path[i+1], 0) in edges_set:
                    edges_set.remove((shortest_path[i], shortest_path[i+1], 0)) # remove
                    edges_set.add((shortest_path[i], shortest_path[i+1], new_value)) # add
                    bfm.update_edge(shortest_path[i], shortest_path[i+1], new_value)
                    break

                if (shortest_path[i+1], shortest_path[i], 0) in edges_set:
                    edges_set.remove((shortest_path[i+1], shortest_path[i], 0)) # remove
                    edges_set.add((shortest_path[i+1], shortest_path[i], new_value)) # add
                    bfm.update_edge(shortest_path[i+1], shortest_path[i], new_value)
                    break

    def modifiedGraphEdges(self, n: int, edges, source: int, destination: int, target: int):
        # Base Case
        indicesToFix = []
        for i in range(len(edges)):
            if edges[i][2] == -1:
                edges[i][2] = float("+inf") # Somehow you can go above the constraint
                # Let me explain
                # Constraint says that wi can be at most 1e7 or 10000000 but QUESTION lets you and wants you to be able to give weights more than that
                # Otherwise how am I supposed to check for this base case????
                indicesToFix.append(i)
        shortest_distance, _ = (self.DijkstraOptimized(edges, n, source, destination)).query_shortest_path()
        if shortest_distance < target: # Even after giving positive infinity to all weights we can change, the shortest distance is still lesser than the target. We won't find any solution, you don't have to process.
            return []
        # Base Case ends

        for i in indicesToFix:
            edges[i][2] = 0
        return self.helperFunction(n, set(tuple(x) for x in edges), source, destination, target, self.DijkstraOptimized(edges, n, source, destination))
2530