Uolevi is working for a construction company that delivers pre-built components to the construction site. As the components can get very wide, it is important to know the maximum width limits for deliveries.

There are $n$ locations numbered $1,2,\dots,n$ and $m$ bidirectional roads numbered $1,2,\dots,m$ connecting them. The $i$-th road connects locations $a_i$ and $b_i$ and has width $w_i$. It is guaranteed that there exists a path between every pair of locations.

The construction company's factory is in location 1. Find the maximum delivery width that can reach each of the locations.

Input

The first line contains two integers $n$ and $m$. The $i$-th of next $m$ following lines contains three integers $a_i$, $b_i$, and $w_i$.

Output

Print the maximum widths that can reach the locations other than the factory in a line, separating with space, like below:

$$\textrm{ans}_1\qquad \textrm{ans}_2\qquad \dots\qquad \textrm{ans}_n$$

Constraints

• $2 \leq n \leq 10^5$
• $n-1 \leq m \leq 2 \times 10^5$
• $q \leq a_i < b_i \leq n$
• $(a_i, b_i) \neq (a_j, b_j)$ if $i \neq j$
• $1 \leq w_i \leq 10^9$

Example 1

Input:

5 5
1 5 8
2 3 5
2 5 10
3 4 4
3 5 6

Output:

8 6 4 8

Example 2

Input:

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

Output:

6 5 1 5 6 5 2 5 1