問題文

$N$ 頂点 $M$ 辺の有向グラフがあります。各頂点は $1$ から $N$ の、各辺は $1$ から $M$ の整数で番号づけられています。 $1\le i\le M$ について、辺 $i$ は頂点 $u_i$ から頂点 $v_i$ へ向かう辺であり、整数 $c_i$ が書かれています。 ここで、 $c_i \in \{0,1\}$ です。また、最初頂点 $1$ にコマが置かれています。

数列 $A$ があり、最初 $A$ は空列です。これからあなたは以下の操作を $0$ 回以上、好きな回数行うことができます。

• 現在コマが頂点 $x$ にあるとする。 $u_e=x$ であるような辺 $e$ を $1$ つ選び、コマを頂点 $v_e$ に移動させる。 そして、 $A$ が空であるか、 $A$ の末尾の要素と $c_e$ が異なるならば、 $A$ の末尾に整数 $c_e$ を追加する。 そうでなければ、( $c_e$ を追加する操作は行わず) $A$ の現在の末尾の要素を削除する。

ただし、頂点 $x$ の出次数が $0$ である場合、操作を行うことはできません。

$k=1,2,\cdots ,N$ のそれぞれについて、コマが頂点 $k$ にある状態における $A$ の長さとしてあり得る最大値を求めてください。 ただし、最大値が存在しない場合 -1 を出力してください。 なお、$1\le v\le N$ なる任意の頂点 $v$ について、頂点 $1$ から頂点 $v$ に到達可能であること、すなわち頂点 $v$ にコマが置かれるような操作列が存在することが制約により保証されます。

制約

• $1\le N\le 2\times 10^5$
• $0\le M\le 2\times 10^5$
• $1\le u_i,v_i\le N\ (1\le i\le M)$
• $c_i \in \{0,1\}\ (1\le i\le M)$
• $(u_i,v_i,c_i) \neq (u_j,v_j,c_j)\ (1\le i < j\le M)$
• $1\le v\le N$ なる任意の頂点 $v$ について、頂点 $1$ から頂点 $v$ へ到達可能
• 入力は全て整数

入力

入力は以下の形式で与えられます。

$N\ M$
$u_1\ v_1\ c_1$
$u_2\ v_2\ c_2$
$\vdots$
$u_M\ v_M\ c_M$

出力

$N$ 行出力してください。 $i$ 行目 $(1\le i\le N)$ にはコマが頂点 $i$ にある状態における $A$ の長さの最大値(ただし存在しない場合は -1 )を出力してください。 最後に改行してください。

サンプル

6 7
1 2 1
2 3 0
3 4 1
4 2 0
1 5 1
5 6 1
6 5 0

0
4
3
3
-1
-1

10 13
1 2 1
2 3 1
3 4 0
4 1 0
2 7 0
3 6 1
4 10 0
10 5 1
5 6 1
6 7 0
7 8 1
8 9 1
9 5 0

0
1
0
1
1
1
2
3
2
0