問題文

$N$ 個の整数からなる数列 $A$ の中央値をつぎのように定義します。

• $A$ を昇順にソートして得られる数列を $A'$ とする。このとき $A'$ の $(N+1)/2$ 番目の要素を $A$ の中央値とする（ $/$ は小数点以下を切り捨てる除算を表す）。

$N$ 頂点 $M$ 辺の重み付き有向グラフがあります。$i\ (1\le i \le M)$ 番目の辺は頂点 $u_i$ から頂点 $v_i$ へ向かっており、重みは $w_i$ です。

頂点 $s$ から頂点 $t$ への 歩道 $p=(v_0=s,e_1,v_1,e_2,\dots,v_{n-1},e_n,v_n=t)$ に対し、 $\mathrm{median}(p)$ を数列 $A=(w_{e_1},w_{e_2},\dots,w_{e_n})$ の中央値とします。

各 $i=2,\ 3,\ \dots\ N$ について、頂点 $1$ から頂点 $i$ への歩道 $p$ に対する $\mathrm{median}(p)$ の最小値を出力してください。歩道が存在しない場合は $-1$ を出力してください。

入力

$N\ M$
$u_1\ v_1\ w_i$
$\vdots$
$u_M\ v_M\ w_M$

• $2 \le N \le 1000$
• $1 \le M \le \min(\frac{N(N-1)}{2},\ 2500)$
• $1 \le u_i,\ v_i \le N\ (1\le i \le M)$
• $1\le w_i \le 10^9\ (1\le i \le M)$
• 与えられる入力はすべて整数
• 与えられるグラフは自己ループや多重辺をもたない

出力

$N-1$ 行出力してください。

$i\ (1\le i \le N-1)$ 行目には頂点 $1$ から頂点 $i+1$ への歩道 $p$ に対する $\mathrm{median}(p)$ の最小値を出力して下さい。 歩道が存在しない場合は $-1$ を出力してください。

最後に改行してください。

サンプル

4 5
1 2 3
2 3 19
3 4 11
1 4 19
2 4 15

3
3
3

8 8
1 2 10
2 3 11
3 4 5
4 5 8
5 3 2
3 6 12
6 7 19
8 5 4

10
5
5
5
5
5
-1

10 20
1 2 12
2 3 81
2 4 50
3 5 98
5 6 75
6 7 15
3 8 40
3 9 75
7 10 86
1 5 11
2 9 99
8 9 12
6 9 96
1 3 93
5 9 37
5 7 17
7 8 96
1 8 49
2 7 79
4 7 82

12
12
12
11
11
11
15
11
15