問題文

あおいちゃんたちの住む国には $N$ 個の町があり、町にはそれぞれ $1$ から $N$ までの番号が割り振られています。
また、町同士をつなぐ一方通行の道が $M$ 本あります。 $i$ 本目 $(1 \leq i \leq M)$ の道では町 $u_i$ から町 $v_i$ へ $t_i$ 分で移動できます。

$N-2$ 人のあおいちゃんたちはお姉ちゃんの頼みでおつかいをします。
$k$ 番目 $(1 \leq k \leq N-2)$ のあおいちゃんは以下のようにおつかいをします。

• 町 $k$ の自宅から出発し、町 $N-1$ と町 $N$ の両方に少なくとも $1$ 回以上訪れ、再び町 $k$ の自宅に戻る。

• $k$ 番目のあおいちゃんのおつかいにかかる時間の最小値を求めてください。
  ただし、おつかいが不可能な場合は-1を出力してください。

制約

• $3 \leq N \leq 2 \times 10^5$
• $0 \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)$
• 入力は全て整数

入力

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

出力

$N-2$ 行出力してください。 $k$ 行目 $(1 \leq k \leq N-2)$ には $k$ 番目のあおいちゃんに対する答えを出力してください。

サンプル

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