You are given a directed graph with ~n~ nodes and ~m~ edges. What is the shortest-path 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~, and ~c~ indicating a directed edge from node ~a~ to node ~b~ with weight ~c~. There may be multiple edges between the same pair of nodes.

The nodes are numbered ~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

Print one line with ~n - 1~ integers: the shortest-path distances to nodes ~2~, ~3~, ~\ldots~, ~n~, in that order, separated by spaces.

Constraints

• ~2 \le n \le 1000~
• ~1 \le m \le 5000~
• ~1 \le a, b \le n~
• ~-10^9 \le c \le 10^9~

Example 1

Input

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

Output

0 1

Explanation

The shortest path to node ~3~ is the direct edge of weight ~1~. The shortest path to node ~2~ is ~1 \to 3 \to 2~ with total weight ~0~.

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