<p>You are given an integer <code>n</code> denoting the number of nodes of a <strong>weighted directed</strong> graph. The nodes are numbered from <code>0</code> to <code>n - 1</code>.</p>

<p>You are also given a 2D integer array <code>edges</code> where <code>edges[i] = [from<sub>i</sub>, to<sub>i</sub>, weight<sub>i</sub>]</code> denotes that there exists a <strong>directed</strong> edge from <code>from<sub>i</sub></code> to <code>to<sub>i</sub></code> with weight <code>weight<sub>i</sub></code>.</p>

<p>Lastly, you are given three <strong>distinct</strong> integers <code>src1</code>, <code>src2</code>, and <code>dest</code> denoting three distinct nodes of the graph.</p>

<p>Return <em>the <strong>minimum weight</strong> of a subgraph of the graph such that it is <strong>possible</strong> to reach</em> <code>dest</code> <em>from both</em> <code>src1</code> <em>and</em> <code>src2</code> <em>via a set of edges of this subgraph</em>. In case such a subgraph does not exist, return <code>-1</code>.</p>

<p>A <strong>subgraph</strong> is a graph whose vertices and edges are subsets of the original graph. The <strong>weight</strong> of a subgraph is the sum of weights of its constituent edges.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/02/17/example1drawio.png" style="width: 263px; height: 250px;" />
<pre>
<strong>Input:</strong> n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5
<strong>Output:</strong> 9
<strong>Explanation:</strong>
The above figure represents the input graph.
The blue edges represent one of the subgraphs that yield the optimal answer.
Note that the subgraph [[1,0,3],[0,5,6]] also yields the optimal answer. It is not possible to get a subgraph with less weight satisfying all the constraints.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/02/17/example2-1drawio.png" style="width: 350px; height: 51px;" />
<pre>
<strong>Input:</strong> n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
<strong>Output:</strong> -1
<strong>Explanation:</strong>
The above figure represents the input graph.
It can be seen that there does not exist any path from node 1 to node 2, hence there are no subgraphs satisfying all the constraints.
</pre>

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

<ul>
	<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= edges.length &lt;= 10<sup>5</sup></code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= from<sub>i</sub>, to<sub>i</sub>, src1, src2, dest &lt;= n - 1</code></li>
	<li><code>from<sub>i</sub> != to<sub>i</sub></code></li>
	<li><code>src1</code>, <code>src2</code>, and <code>dest</code> are pairwise distinct.</li>
	<li><code>1 &lt;= weight[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        """
        Intuition:
            1) if src1, src2 DON'T share any paths: cost is the sum of the minimum paths
            2) if they do share weights, we "save" the cost of the shared edges.
            
        cost := sum of path1 + sum of path2 - sum of shared weights
            
        Difficulty: we might take a suboptimal path1 and path2 for the sake of sharing weights.
            
        This makes me think two iterative dijkstra's:
            1) we first iterate from src1 to dest
            2) we then iterate from src2 to dest, assuming that once we've hit an existing path, the cost of traversing this node is simply the existing cost.
        
        Need to flesh out some details, including, why we don't start from dest and do one dijkstra.
        
        Why this might not work:
        1) dijkstra := shortest path from src1 to each node, as opposed to shortest path from node --> src1.
        -----------------------
        
        Consider the set of nodes along this path:
            Either: path 1 goes through path 2, WLOG
            Or: they intersect at some common node.
        
        ------------------------
        
        Then: the question becomes finding: find the first shared node.
        
        We could do "reverse" dijkstra's from node 0, which finds the shortest path from that node to every node.
        
        We do a dijkstra's from src1/2 to every node
        
        Then, we iterate over all possible starting shared paths, add d1 + d2, then take minimum.
        
        Why does this algorithm terminate at optimal?
            Edge weights are non-negative => we might have suboptimal, i.e., if we look at 4, we double count 3->4. but when we look at 3, we're happy!
            
        1 -->
               3 --> 4 --> d
        2 -->
        
        This is 3 dijkstra's!
        """
        dist1 = [float("inf")] * n
        dist2 = [float("inf")] * n
        distd = [float("inf")] * n
        
        # going to dest
        forward_adjlist = [[] for _ in range(n)]
        # starting from dest
        backward_adjlist = [[] for _ in range(n)]
        
        for start, end, weight in edges:
            forward_adjlist[start].append((weight, end))
            backward_adjlist[end].append((weight, start))
        
        def dijkstra(start, dist, adjList):
            # uses the first key
            h = adjList[start][:]
            heapq.heapify(h)
            # print("------", start, h)
            
            dist[start] = 0
            visited_count = 1
            
            while h:
                d, node = heapq.heappop(h)
                # print(d, node)
                
                # functions as visited set.
                if dist[node] < float("inf"):
                    continue
                    
                dist[node] = d

                visited_count += 1
                if visited_count == n:
                    return
                
                for weight, neigh in adjList[node]:
                    # print(node, adjList[node])
                    if dist[neigh] == float("inf"): # not visited yet
                        heapq.heappush(h, (d + weight, neigh))
            
        dijkstra(src1, dist1, forward_adjlist)
        dijkstra(src2, dist2, forward_adjlist)
        dijkstra(dest, distd, backward_adjlist)
            
        # from pprint import pprint
        # pprint(dist1)
        # pprint(dist2)
        # pprint(distd)
            
        res = float("inf")
        for i in range(n):
            res = min(res, dist1[i] + dist2[i] + distd[i])
        return res if res < float("inf") else -1
            
82100