Copy Paste 3???

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

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

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

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

7 14 18 21 19 27 36 21 22