284. Shortest Path (Weighted)
MediumDijkstra
Print the shortest distance from node 1 to every node of the undirected weighted graph (non-negative weights), or -1 for unreachable nodes.
Input format
Line 1: n m Next m lines: u v w
Output format
n distances.
Example 1
Input
5 6 1 2 2 1 3 4 2 3 1 2 4 7 3 5 3 4 5 1
Output
0 2 3 7 6
Example 2
Input
3 1 1 2 5
Output
0 5 -1
Constraints
1 ≤ n ≤ 10⁵ 0 ≤ w ≤ 10⁹
Read input from standard input and print the answer to standard output. Your code is judged against 4 test cases, most of them hidden.
Loading the MyLoginn IDE…