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 and that there are no negative cycles.

Output

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

Constraints

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

Example 1

Input

3 3
1 2 2
1 3 1 
3 2 -1

Output

0 1

Example 2

Input

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

Output

7 14 18 21 19 27 36 21 22