Problem G
Gauntlet of Fire

Spike is competing in the Gauntlet of Fire for the title of Dragon Lord. To succeed, he needs to traverse the labyrinthine volcanic tunnels, avoiding the treacherous elements and making it from chamber to chamber as quickly as possible.

The cave has $N$ chambers and $M$ tunnels connecting these chambers; no tunnel connects a chamber to itself, and there is at most one tunnel between any two chambers. This cave has a special property: it is known that it is possible to travel between any two different chambers by taking one or more tunnels, and that there are at most two paths between any two different chambers that do not take any tunnel more than once.

For simplicity, we label the chambers $1, 2, \dots , N$; then, the $i^\text {th}$ tunnel connects chambers $A_ i$ and $B_ i$, and has a length of $L_ i$ meters.

Spike can travel at the fast, fast speed of $1$ meter per second. He wants to know the danger level of each chamber. The danger level of a chamber is simply the sum of the times, in seconds, required to travel from this chamber to every other chamber, assuming that one always takes the shortest path possible.

Help Spike determine the danger level of each chamber!

Since these numbers can be quite large, you should output only the remainders after dividing each number by $10^9+7$.

Input

The first line of input contains two integers, $N$ ($2 \leq N \leq 200\, 000$) and $M$ ($N-1 \leq M \leq 400\, 000$) the number of chambers and tunnels in the cave.

The next $M$ lines contain the descriptions of the tunnels. In particular, the $i^\text {th}$ of these lines contains three integers $A_ i$, $B_ i$ ($1\leq A_ i, B_ i \leq N$; $A_ i \neq B_ i$) and $L_ i$ ($1 \leq L_ i \leq 10^9$), denoting that the $i^\text {th}$ tunnel connects chambers $A_ i$ and $B_ i$, and has a length of $L_ i$ meters.

It is guaranteed that there is at most one tunnel between any two chambers, that it is possible to travel between any two different chambers by taking one or more tunnels, and that there are at most two paths between any two chambers that do not take any tunnel more than once.

Output

Output $N$ integers on a single line, separated by spaces. The $i^\text {th}$ of these integers should contain the danger level of chamber $i$.

Since these numbers can be quite large, you should output only the remainders after dividing each number by $10^9+7$.

5 5
1 2 3
1 4 8
2 3 12
3 5 4
4 5 2

35 39 36 27 29

7 6
1 2 8
1 3 15
1 4 10
3 5 40
3 6 3
5 7 60

221 261 206 271 326 221 626