Shortest Paths

You are given a graph of n nodes and m undirected edges. Find the shortest path from node 1 to each node with Dikjstra's algorithm.

Input

The first line contains two integers n and m (2≤n≤100,0≤m≤n(n−1)2).

The following m lines contain 3 integers each: u, v, and w, denoting an undirected edge from u to v with weight w (1≤u,v≤n,0≤w≤105).

Output

Output the shortest path from node 1 to each node 2,…,n. If a node is not reachable from node 1, output −1.

2 1
1 2 1

1

5 5
1 2 7
1 3 4
1 4 9
2 3 6
3 4 2

7
4
6
-1

5 6
1 5 2
2 1 6
3 4 2
4 2 9
5 3 7
2 3 4

6
9
12
2