002 - PRO製造機

時間制限 1 秒 / メモリ制限 32 MB / 得点 100 / x 6 /


TLE
1sec
MLE
32MB
得点
100

もんだい

あるH工場では、"PRO"を製造しています。
倒産してしまいそうなこの工場は"PRO"を効率よく生産することが大切です。
なので、効率よく生産するために、"PRO"を作る材料を計画的に揃えることにしました。
この工場では、最終的に製造する"PRO"を製品番号 N とし、製品番号 1 〜 N-1 の材料となる製品を取り扱っています。

1〜N-1 の製品は購入するか、この工場で製造するかのどちらかにより入手することにしています。
この工場はプライドが高いせいか、あまり製品を購入することは好きではありません。
なので"PRO"である製品 N も含めて、製造できる製品は購入せずに、必ず製造することにしています。

しょうさい

入力に各製品の製造方法が与えられるので、"PRO"である製品 N を1個作るために、購入する必要のある最小の個数を1〜N-1番の製品ごとにそれぞれ1行で出力してください。


製品iの製造方法が複数与えられた場合は、それらすべての材料を必要とします。
また、製品Nを製造するための製造方法は必ず与えられるとします。

にゅうりょく

N
M
P1 Q1 R1
P2 Q2 R2
   :
PM QM RM

1行目に、製品の個数 N (2 ≦ N ≦ 100) が与えられる。
2行目に、製造方法の数 M (1 ≦ M ≦ 350) が与えられる。
3行目からM+2行目までに、製造方法を表す3つの整数が空白区切りで与えられる。
Pi : 材料の製品番号 (1 ≦ Pi ≦ N)
Qi : 材料の個数 (1 ≦ Qi ≦ 100)
Ri : 製造する製品番号 (1 ≦ Ri ≦ N)

しゅつりょく

製造番号1の購入数 (S1)
製造番号2の購入数 (S2)
:
製造番号iの購入数 (Si)
:
製造番号N-1の購入数 (SN-1)

Si は "232-1" (4294967295) を超えることはない。

さんぷる

入力例1

2
1
1 5 2

出力例1

5

解説

"PRO"(製品2)を作るためには製品1が5個必要である。
製品1を製造する方法がないため、製品1を5個買うことになる。

入力例2

4
3
1 1 2
2 3 4
3 1 4

出力例2

3
0
1

解説

"PRO"(製品4)を作るためには製品2が3個と、製品3が1個必要である。
製品2は製品1を1個使って製造できるので、製品1を3個買って製品2を3個作る。
製品3は製造する方法がないため、製品3を1個買うことになる。

入力例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

出力例3

0
0
5814
0
0
0
11827308
0