Shortest Path

You are given a weighted, directed graph with n nodes labeled 0 to n - 1, described by a list of edges edges where edges[i] = [u, v, weight] means there is a directed edge from u to v with a non-negative weight weight. Given a source node, return an array dist where dist[i] is the length of the shortest path from source to node i, or -1 if node i is unreachable.

Example 1

Input: n = 5, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]], source = 0

Output: [0, 3, 1, 4, 7] — the shortest path to node 1 goes 0 -> 2 -> 1 (cost 1 + 2 = 3), not the direct edge 0 -> 1 (cost 4).

Example 2

Input: n = 3, edges = [[0,1,1]], source = 0

Output: [0, 1, -1] — node 2 is unreachable from node 0.

Constraints

• 1 <= n <= 10^4
• 0 <= edges.length <= 10^5
• 0 <= weight <= 10^4 (all weights are non-negative)
• 0 <= source < n