Problem Statement

Taro is planning to build a certain factory.
To produce efficiently, he must purchase materials according to a plan.
In this factory, the final product to be manufactured has product number \(N\),
and the products with product numbers \(1\) to \(N-1\) are handled as intermediate materials.

Each product with product numbers \(1\) to \(N-1\) can be obtained either by purchasing it externally
or by manufacturing it in this factory.
Also, any product that can be manufactured, including the final product \(N\), is always manufactured and never purchased externally.

The input gives the manufacturing methods for the product numbers (\(1\) to \(N\)) (the product number and quantity of a material, and the product number of which \(1\) unit can be manufactured from that material).
Find the minimum quantity that must be purchased externally in order to make \(1\) unit of the final product \(N\), and output it
for each of the product numbers \(1\) to \(N-1\), on \(1\) line each.

If multiple manufacturing methods are listed for product \(i\), all of those materials are required.
A manufacturing method for product \(N\) is always given.

Input

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

The \(1\)st line contains an integer \(N\ (2 \leq N \leq 100)\), the number of product types.
The \(2\)nd line contains an integer \(M\ (1 \leq M \leq 1500)\), the number of manufacturing methods.
Each of the following \(M\) lines contains 3 space-separated integers describing a manufacturing method: the product number of the material \(P_i\), the quantity of the material \(Q_i\), and the product number to be manufactured \(R_i\).
\(1 \leq P_i \lt N\), \(1 \leq Q_i \leq 100\), \(1 \leq R_i \leq N\)

If \(1 \leq i \leq M\), \(i \neq j\), then \((P_i,R_i) \neq (P_j,R_j)\)
For every \(R_i\),
\(R_i\) never requires \(R_i\) itself as a material (or as a material of a material, and so on).

Output

Purchase quantity of product number \(1\) \((S_1)\)
Purchase quantity of product number \(2\) \((S_2)\)
\(\dots\)
Purchase quantity of product number \(i\) \((S_i)\)
\(\dots\)
Purchase quantity of product number \(N-1\) \((S_{N-1})\)

Output \(N-1\) lines in the format above. Output a newline at the end of each line.
\(S_i\) never exceeds \(4294967295 (2^{32}-1)\).

Sample

Sample 1

Input

2
1
1 5 2

Output

5

There is only \(1\) manufacturing method, and making the final product (number \(2\)) requires
\(5\) units of the intermediate material (number \(1\)).
Number \(1\) cannot be manufactured, so outputting that \(5\) units of it are purchased is correct.

Sample 2

Input

4
3
1 1 2
2 3 4
3 1 4

Output

3
0
1

Making the final product (number \(4\)) requires product \(2\) in a quantity of \(3\) and product \(3\) in a quantity of \(1\).
Product \(2\) can be manufactured from product \(1\), so in the end, product \(1\) in a quantity of \(3\) and product \(3\) in a quantity of \(1\) are required.
For a product that is not purchased, you must output \(0\).

Sample 3

Input

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

Output

0
0
5814
0
0
0
11827308
0