Single-Source Shortest Distances

You are given a directed weighted graph with n nodes labeled 1 to n, described by an array edges, where edges[i] = [a, b, c] is a one-way edge from node a to node b of length c. The graph may contain self-loops and multiple edges between the same pair of nodes.

It is guaranteed that every node is reachable from node 1.

Return an array of n integers whose entry at index i (0-based) is the length of the shortest path from node 1 to node i + 1. The first entry is always 0.

Examples

Example 1

Input: n = 3, edges = [[1,2,6],[1,3,2],[3,2,3],[1,3,4]]
Output: [0,5,2]
Explanation: The shortest path to node 3 is the direct edge 1 -> 3 of length 2 (cheaper than the parallel edge of length 4). The shortest path to node 2 is 1 -> 3 -> 2 with length 2 + 3 = 5, cheaper than the direct edge of length 6.

Example 2

Input: n = 4, edges = [[1,2,5],[2,4,2],[1,3,9],[3,4,1],[1,4,8]]
Output: [0,5,9,7]
Explanation: Node 4 is reached cheapest via 1 -> 2 -> 4 with length 5 + 2 = 7, beating the direct edge (8) and the route through node 3 (9 + 1 = 10).