Solve the Single Source Shortest Path problem.

Input Specification

Line ~1~: ~N~ ~(2 \le N \le 1\,000)~ (vertices), ~M~ ~(1 \le M \le 5\,000)~ (bidirectional edges)

Lines ~2~ to ~M+1~: ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le N, 1 \le w_i \le 10\,000)~, a bidirectional edge from ~u_i~ to ~v_i~ with weight ~w_i~. Multiple edges between the same pair of vertices may occur in the input.

Output Specification

Lines ~1~ to ~N~: line ~i~ has the length of the shortest path from vertex ~1~ to vertex ~i~. If no path exists, output -1.

Sample Input

4 3
1 2 2
1 3 5
2 3 2

Sample Output

0
2
4
-1