Copy Paste

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

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

4 5 7 8 

Example 2

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

10 12 18 20 15 12 19 1 11