You are given a directed graph with ~n~ nodes and ~m~ edges. What is the distance from node ~1~ to every other node.

Input

The first line contains the integers ~n~ and ~m~. The following ~m~ lines contain integers ~a, b, c~ indicating a directed edge from node ~a~ to node ~b~ with weight ~c~. The nodes are numbers ~1~ through ~n~.

It is guaranteed that there is a path from ~1~ to every other node.

Output

A line containing the distances to each node ~2~ through ~n~.

Constraints

• ~1 \le a,b \le n \le 10000~
• ~1 \le c \le 10^9~
• ~1 \le m \le 10^5~

Example 1

Input

5 10
1 2 4
2 3 4
3 4 2
4 5 3
5 1 2
4 5 1
3 1 1
5 2 1
2 3 1
2 3 1

Output

4 5 7 8

Example 2

Input

10 20
1 2 10
2 3 8
3 4 10
4 5 8
5 6 9
6 7 1
7 8 7
8 9 4
9 10 10
10 1 1
8 5 1
6 4 3
10 3 1
3 6 3
10 9 2
1 9 1
8 5 2
10 7 1
5 3 1
7 7 2

Output

10 12 18 20 15 12 19 1 11