問題文

太郎君はとある工場を建てようとしています。
効率よく生産するためには、材料を計画的に購入しなければなりません。
この工場では、最終的に製造したい製品を 製品番号\(N\) とし、
製品番号\(1\) ～ \(N-1\) の中間素材となる製品を取り扱います。

製品番号\(1\) ～ \(N-1\) の製品は、外部から購入するか、
またはこの工場で製造するかのどちらかにより手に入るものとします。
また、最終製品\(N\)も含め製造することが出来る製品は、外部から購入せずに必ず製造するものとします。

入力に、各製品番号(\(1\)～\(N\))の製造方法（材料の製品番号・個数と、その材料から\(1\)個製造できる製品番号）
が与えられるので、最終製品\(N\)を\(1\)個作るために、外部から購入する必要のある最小の個数を
\(1\)～\(N-1\)番の 製品番号ごとにそれぞれ\(1\)行で出力してください。

製品\(i\)の製造方法が複数書かれている場合は、それらすべての材料が必要です。
製品\(N\)を製造するための製造方法は必ず与えられます。

入力

\(N\)
\(M\)
\(P_1\ Q_1\ R_1\)
\(P_2\ Q_2\ R_2\)
\(\dots\)
\(P_M\ Q_M\ R_M\)

\(1\)行目に、製品の種類数を表す整数 \(N\ (2 \leq N \leq 100)\) が与えられる。
\(2\)行目に、製造方法の数を表す整数 \(M\ (1 \leq M \leq 1500)\) が与えられる。
続く\(M\)行に、製造方法を表す3つの整数、材料の製品番号\(P_i\)、材料の個数\(Q_i\)、製造する製品番号\(R_i\)がスペース区切りで与えられる。
\(1 \leq P_i \lt N\)、\(1 \leq Q_i \leq 100\)、\(1 \leq R_i \leq N\)

\(1 \leq i \leq M\)、\(i \neq j\) ならば \((P_i,R_i) \neq (P_j,R_j)\)
すべての\(R_i\)について、
\(R_i\)の材料(および材料の材料、…)として\(R_i\)自身を必要とすることはありません。

出力

製品番号\(1\) の購入数\((S_1)\)
製品番号\(2\) の購入数\((S_2)\)
\(\dots\)
製品番号\(i\) の購入数\((S_i)\)
\(\dots\)
製品番号\(N-1\) の購入数\((S_{N-1})\)

となるように \(N-1\)行出力してください。行の末尾には改行を出力してください。
\(S_i\)は \(4294967295 (2^{32}-1)\)を超えることはありません。

サンプル

サンプル1

入力

2
1
1 5 2

出力

5

製造方法の数は\(1\)つだけで、最終製品(番号\(2\))を作るためには、
中間素材(番号\(1\))の材料が\(5\)個必要です。
番号\(1\)は製造できないので、これを\(5\)個購入すると出力すれば正解です。

サンプル2

入力

4
3
1 1 2
2 3 4
3 1 4

出力

3
0
1

最終製品(番号\(4\))を作るためには、製品\(2\)が\(3\)個と、製品\(3\)が\(1\)個必要になります。
製品\(2\)は製品\(1\)から製造できるので、最終的に、製品\(1\)が\(3\)個と製品\(3\)が\(1\)個必要となります。
購入しない製品は\(0\)を出力する必要があります。

サンプル3

入力

9
10
1 11 2
7 12 8
8 13 1
2 14 9
8 15 9
8 16 4
3 17 4
4 18 5
5 19 9
2 20 4

出力

0
0
5814
0
0
0
11827308
0