Problem Statement

The country where Aoi-chan and the others live has $N$ towns, numbered from $1$ to $N$.
There are also $M$ one-way roads connecting the towns. The $i$-th road $(1 \leq i \leq M)$ lets you travel from town $u_i$ to town $v_i$ in $t_i$ minutes.

At their older sister's request, $N-2$ Aoi-chans go on errands.
The $k$-th $(1 \leq k \leq N-2)$ Aoi-chan does her errand as follows.

• She departs from her home in town $k$, visits both town $N-1$ and town $N$ at least $1$ time each, and returns to her home in town $k$.

• Find the minimum time required for the errand of the $k$-th Aoi-chan.
  If the errand is impossible, output -1.

Constraints

• $3 \leq N \leq 2 \times 10^5$
• $N \leq M \leq \min(2 \times 10^5, N(N-1))$
• $1 \leq u_i, v_i \leq N$
• $1 \leq t_i \leq 10^9$
• $u_i \ne v_i$
• $i \ne j \Longrightarrow (u_i, v_i) \ne (u_j, v_j)$
• All input values are integers.

Input

$N$ $M$
$u_1$ $v_1$ $t_1$
$u_2$ $v_2$ $t_2$
$\vdots$
$u_M$ $v_M$ $t_M$

Output

Output $N-2$ lines. On the $k$-th line $(1 \leq k \leq N-2)$, output the answer for the $k$-th Aoi-chan.

Sample

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

33
25
33

10 23
7 3 75
2 1 26
5 7 52
1 9 51
8 1 4
1 3 73
7 8 11
6 7 46
10 3 19
6 1 13
1 2 46
9 6 52
10 6 12
5 6 65
9 4 44
7 10 19
5 9 13
3 6 56
8 7 87
3 7 95
2 3 35
9 2 43
1 10 3

144
148
207
-1
-1
144
192
192