<p>You are given an undirected weighted graph of <code>n</code> nodes numbered from 0 to <code>n - 1</code>. The graph consists of <code>m</code> edges represented by a 2D 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>Consider all the shortest paths from node 0 to node <code>n - 1</code> in the graph. You need to find a <strong>boolean</strong> array <code>answer</code> where <code>answer[i]</code> is <code>true</code> if the edge <code>edges[i]</code> is part of <strong>at least</strong> one shortest path. Otherwise, <code>answer[i]</code> is <code>false</code>.</p>

<p>Return the array <code>answer</code>.</p>

<p><strong>Note</strong> that the graph may not be connected.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/03/05/graph35drawio-1.png" style="height: 129px; width: 250px;" />
<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[true,true,true,false,true,true,true,false]</span></p>

<p><strong>Explanation:</strong></p>

<p>The following are <strong>all</strong> the shortest paths between nodes 0 and 5:</p>

<ul>
	<li>The path <code>0 -&gt; 1 -&gt; 5</code>: The sum of weights is <code>4 + 1 = 5</code>.</li>
	<li>The path <code>0 -&gt; 2 -&gt; 3 -&gt; 5</code>: The sum of weights is <code>1 + 1 + 3 = 5</code>.</li>
	<li>The path <code>0 -&gt; 2 -&gt; 3 -&gt; 1 -&gt; 5</code>: The sum of weights is <code>1 + 1 + 2 + 1 = 5</code>.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/03/05/graphhhh.png" style="width: 185px; height: 136px;" />
<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 4, edges = [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[true,false,false,true]</span></p>

<p><strong>Explanation:</strong></p>

<p>There is one shortest path between nodes 0 and 3, which is the path <code>0 -&gt; 2 -&gt; 3</code> with the sum of weights <code>1 + 2 = 3</code>.</p>
</div>

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

<ul>
	<li><code>2 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>m == edges.length</code></li>
	<li><code>1 &lt;= m &lt;= min(5 * 10<sup>4</sup>, n * (n - 1) / 2)</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li><code>1 &lt;= w<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
	<li>There are no repeated edges.</li>
</ul>

import heapq
def dijkstra(src, adj_list, n):
    distance = [int(1e9) for i in range(n)]
    pq = set()
    distance[src] = 0
    pq.add((0, src))

    while len(pq) > 0:
        dist, node = pq.pop()

        for pair in adj_list[node]:
            adj_node = pair[0]
            edge_wt = pair[1]

            if dist + edge_wt < distance[adj_node]:
                distance[adj_node] = dist + edge_wt
                pq.add((distance[adj_node], adj_node))
        
    return distance
        

class Solution:
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        adj_list = {}
        for i in range(n):
            adj_list[i] = []
        
        for x in edges:
            adj_list[x[0]].append((x[1], x[2]))
            adj_list[x[1]].append((x[0], x[2]))

        src_zero = dijkstra(0, adj_list, n)
        if src_zero[n-1] == int(1e9):
            return [False for i in range(len(edges))]
        src_last = dijkstra(n-1, adj_list, n)

        # print(src_zero, src_last)
        results = []
        for each_edge in edges:
            if src_zero[each_edge[0]] + src_last[each_edge[1]] + each_edge[2] == src_zero[n-1]:
                results.append(True)
            elif src_zero[each_edge[1]] + src_last[each_edge[0]] + each_edge[2] == src_zero[n-1]:
                results.append(True)
            else:
                results.append(False)
        
        return results

# class Solution:
#     def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:

#         def dijk(root: int) -> list[int]:

#             wgts, heap = [inf] * n, [(0, root)]
#             wgts[root] = 0
          
#             while heap:

#                 wgt1, node1 = heappop(heap)
#                 if wgts[node1] != wgt1: continue

#                 for wgt2, node2 in graph[node1]:
#                     smWght = wgt1 + wgt2

#                     if smWght >= wgts[node2]:  continue
#                     wgts[node2] = smWght
#                     heappush(heap, (smWght, node2))

#             return wgts


#         graph, ans = defaultdict(list), []
#         beg, end = 0, n-1

#         for node1, node2, wgt in edges: 
#             graph[node1].append((wgt, node2))
#             graph[node2].append((wgt, node1))
        
#         fromBegto = dijk(beg)
#         if fromBegto[end] == inf:  return [False]*len(edges)

#         toEndfrom = dijk(end)
        
#         for node1, node2, wgt in edges:
#             mn = min(fromBegto[node1] + toEndfrom[node2], 
#                      fromBegto[node2] + toEndfrom[node1])
#             ans.append(mn + wgt == fromBegto[end])
            
#         return ans
52900