Problem E
Catching Noodles

Historians record an age where humans were once able to cough in public and eat out with friends. Of interest today is the tradition of Nagashi Sōmen, where noodles are “place(d) in a long flume of bamboo… As (they) pass by, diners pluck them out with their chopsticks”. For research purposes, you would like to reenact this tradition of catching noodles.

To catch a noodle, you have to think like a noodle! Noodles start their journey from junction $0$ and escape at junction $j-1$. Junctions are connected by bamboos of varying lengths. To avoid being captured, each noodle takes the route of minimal length. You would like to figure out the best junction to catch the most noodles by determining the number of unique routes noodles may take through each junction.

Refer to the diagram below for clarification on how the routes are counted for the Sample Input 4.

Input

The first line contains $2$ integers $1 \le j \le 10^5$ junctions and $1 \le b \le 10^6$ bamboos. The next $b$ lines describe bamboos connecting two different junctions. Each line contains $3$ integers $u\; v\; l$ denoting junctions $0 \le u, v < j$ and length $1 \le l \le 10^5$.

Output

On one line, output the number of unique routes through each junction. If no routes pass through a junction, print $-1$. Because the number of routes can be large, print the answer for each junction $\bmod (10^9 + 7)$.

Note that

Subtasks

1. ($4$ Points): Sample Input 1/2/3/4 (with different $b$) corresponds to Subtask 2/3/4/6. Each worth 1 point.

2. ($24$ Points): There is at most $1$ route between any $2$ junctions.

3. ($24$ Points): All bamboos have the same length, and there is at most $1$ shortest route from junction $0$ to $j-1$.

4. ($24$ Points): There is at most $1$ shortest route from junction $0$ to $j-1$.

5. ($12$ Points): All bamboos have the same length.

6. ($12$ Points): No additional constraints.

5 3
0 2 2
1 2 1
2 4 1

1 -1 1 -1 1

5 4
0 1 1
0 2 1
1 2 1
2 4 1

1 -1 1 -1 1 

5 5
0 1 1
0 2 3
1 2 1
1 4 3
2 4 1

1 1 1 -1 1

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

3 2 2 -1 3