問題文

$N$ 頂点 $M$ 辺の重み付き有向グラフ $G$ が与えられます。$G$ は自己ループ、負閉路を持ちません。 $i \,\, (1 \leqq i \leqq M)$ 番目の辺は頂点 $s_i$ から頂点 $t_i$ に向けて張られており、重みは $d_i$ です。

頂点 $i$ からいくつかの辺を辿って到達できる各頂点 $j$ について、頂点 $i$ から頂点 $j$ まで辺を辿って移動するときの辺の重みの総和の最小値を $D_{i,j}$ とします。ただし、 $i = j$ または頂点 $i$ から頂点 $j$ にたどり着けない場合は $D_{i,j} = 0$ とします。

このとき、各 $i\ (1 \leq i \leq N)$ について、$\displaystyle \sum_{j=1}^{N} D_{i,j}$ を求めてください。

入力

$N\ M$
$s_1\ t_1\ d_1$
$s_2\ t_2\ d_2$
$\vdots$
$s_M\ t_M\ d_M$

• 入力は全て整数である。
• $2 \leqq N \leqq 100$
• $1 \leqq M \leqq 9900$
• $1 \leqq s_i,t_i \leqq N$
• $s_i \neq t_i$
• $-10^{12} \leqq d_i \leqq 10^{12}$
• $G$ は負閉路を持たない。

出力

$N$ 行にわたって出力してください。

$i\ (1 \leqq i \leqq N)$ 行目には、$\displaystyle \sum_{j=1}^{N} D_{i,j}$ を出力してください。 最後に改行してください。

サンプル

4 5
3 4 3
2 1 2
4 2 6
3 1 1
1 3 1

15
11
13
23

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

12
3
-16
17
16

4 6
1 2 1
1 3 -5
2 3 2
2 4 4
3 4 1
4 3 7

-8
5
1
7