Problem Statement

You are given a weighted directed graph $G$ with $N$ vertices and $M$ edges. $G$ has no self-loops and no negative cycles. The $i \,\, (1 \leqq i \leqq M)$-th edge goes from vertex $s_i$ to vertex $t_i$ and has weight $d_i$.

For each vertex $j$ reachable from vertex $i$ by following some edges, let $D_{i,j}$ be the minimum total edge weight when moving from vertex $i$ to vertex $j$ along edges. However, if $i = j$ or vertex $j$ cannot be reached from vertex $i$, let $D_{i,j} = 0$.

Find $\displaystyle \sum_{j=1}^{N} D_{i,j}$ for each $i\ (1 \leq i \leq N)$.

Input

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

• All inputs are integers.
• $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$ has no negative cycles.

Output

Output $N$ lines.

On the $i\ (1 \leqq i \leqq N)$-th line, output $\displaystyle \sum_{j=1}^{N} D_{i,j}$. Print a newline at the end.

Sample

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