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

    const int INF = 2e9;

    void processDijkstrasNode(int node, int dist[], bool vis[], vector<vector<pair<int, int> > >& adjl, priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >& pq) {
        vector<pair<int, int> > neighbours = adjl[node];
        vis[node] = true;
        int nodeDist = dist[node];
        int neighbour, neighbourDist;
        for (int i = 0; i < neighbours.size(); i++) {
            neighbourDist = nodeDist + neighbours[i].second;
            neighbour = neighbours[i].first;
            if (neighbourDist < dist[neighbour]) {
                dist[neighbour] = neighbourDist;
                pq.push({neighbourDist, neighbour});
            }
        }
    }
    
    int runDijkstras(vector<vector<pair<int, int> > >& adjl, int n, int src, int dest) {
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        int dist[n];
        bool vis[n];
        fill(dist, dist + n, INF);
        fill(vis, vis + n, false);

        dist[src] = 0;
        pq.push({0, src});

        while (!pq.empty()) {
            pair<int, int> node = pq.top();
            pq.pop();

            if (vis[node.second]) {
                continue;
            }
            if (dest == node.second) {
                break;
            }
            processDijkstrasNode(node.second, dist, vis, adjl, pq);
        }

        return dist[dest];
    }

    vector<vector<int> > convertToVectorOfEdges(vector<vector<pair<int, int> > >& adjl) {
        vector<vector<int > > edges;
        int n = adjl.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < adjl[i].size(); j++) {
                if (adjl[i][j].first < i) {
                    continue;
                }
                edges.push_back({i, adjl[i][j].first, adjl[i][j].second});
            }
        }
        return edges;
    }

    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
        list<pair<int, int> > negEdges;
        vector<vector<pair<int, int> > > adjl(n, vector<pair<int, int> >());
        int u, v, w;

        for (int i = 0; i < edges.size(); i++) {
            u = edges[i][0];
            v = edges[i][1];
            w = edges[i][2];

            if (w == -1) {
                negEdges.push_back({u, v});
                continue;
            }
            adjl[u].push_back({v, w});
            adjl[v].push_back({u, w});
        }

        // Check 1 - Shortest distance without using negative edges
        int dist = runDijkstras(adjl, n, source, destination);
        bool isTargetMatching = false;
        // If dist is less than target, then reaching target is not possible as we can only increase the distance via negEdges but shortest path will always be shorter than that.
        if (dist < target) {
            cout << dist << endl;
            return {};
        } else if (dist == target) {
            isTargetMatching = true;
            // return convertToVectorOfEdges(adjl);
        }

        // // NOT DOING THIS - Check 2 - Shortest distance with negative edges at min value, i.e. 1
        // for (auto edge : negEdges) {
        //     u = edge.first;
        //     v = edge.second;
        //     adjl[u][v] = 1;
        //     adjl[v][u] = 1;
        // }
        // dist = runDijkstras(adjl, n, source, destination);
        // // If dist is greater than target, then reaching target is not possible as we can only further increase the distance via negEdges.
        // if (dist != INF && dist > target) {
        //     cout << dist << endl;
        //     return {};
        // }

        // Finding the solution
        // // NOT DOING AS EDGES NOT ADDED NOW We set all edges to INF
        // for (pair<int, int> edge : negEdges) {
        //     u = edge.first;
        //     v = edge.second;
        //     adjl[u][v] = INF;
        //     adjl[v][u] = INF;
        // }

        // Set edges one by one until the shortest distance becomes lesser than target.
        for (pair<int, int> edge : negEdges) {
            u = edge.first;
            v = edge.second;
            if (isTargetMatching) {
                adjl[u].push_back({v, INF});
                adjl[v].push_back({u, INF});
                continue;
            }

            adjl[u].push_back({v, 1});
            adjl[v].push_back({u, 1});
            dist = runDijkstras(adjl, n, source, destination);

            // If dist is less than target after setting this edge weight as 1, this means that the shortest path passes through this edge (condition would activate for the 
            // first edge which does so)
            // We can update the weight for this node to match the target. It's not possible for there to be a shorter path connecting u and v (as it would already have been taken 
            // previously when processing previous edges)
            if (dist <= target) {
                int updatedWeight = 1 + target - dist;
                adjl[u].pop_back();
                adjl[v].pop_back();
                adjl[u].push_back({v, updatedWeight});
                adjl[v].push_back({u, updatedWeight});
                // cout << u << " " << v << " " << updatedWeight << endl;
                isTargetMatching = true;
            }
        }
        if (!isTargetMatching) {
            return {};
        }
        return convertToVectorOfEdges(adjl);
    }
};
542372