You are given an undirected graph with ~n~ vertices and ~m~ edges. Your task is to calculate the shortest path length from vertex ~0~ to other vertices and print them, if there is no path, print out -1.

Input

• First line contains ~n~ and ~m~ ~(n, m \le 10^5)~
• Next ~m~ lines, each line contains three integers represent for and edge: vertex1, vertex2 and length

Output

• Print out shortest path length from vertex ~0~ to other vertices

Example Input

5 35 3
0 3 55
2 1 3
2 0 78

Example Output

81 78 55 -1