Problem Description

There is a directed graph with $n$ vertices and $m$ edges.

For each edge, calculate the number of times it is traversed by the shortest paths between any two points, modulo $10^9+7$.

If there are multiple shortest paths between points $A$ and $B$, each shortest path must be counted. You can refer to the output of the 3rd and 4th edges in Sample 4 to understand this statement.

Input Format

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain three integers $x$, $y$, and $d$, indicating a directed edge from $x$ to $y$ with weight $d$.

Output Format

There are $m$ lines in total. Each line outputs an integer, where the number on the $i$-th line represents the number of times the edge described in the $(i+1)$-th line of input is traversed by the shortest paths between any two points, modulo $10^9+7$.

Sample Input and Output

Input Sample #1

4 3
1 2 5
2 3 5
3 4 5

Output Sample #1

3
4
3

Input Sample #2

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

Output Sample #2

2
3
2
1

Input Sample #3

5 8
1 2 20
1 3 2
2 3 2
4 2 3
4 2 3
3 4 5
4 3 5
5 4 20

Output Sample #3

0
4
6
6
6
7
2
6

Input Sample #4

4 4
1 2 1
2 3 1
1 3 2
3 4 1

Output Sample #4

3
4
2
4

Notes

Data Range and Constraints

• For $30\%$ of the data, $n \le 15$ and $m \le 30$.
• For $60\%$ of the data, $n \le 300$ and $m \le 10^3$.
• For $100\%$ of the data, $1 \le n \le 1.5 \times 10^3$, $1 \le m \le 5 \times 10^3$, $a \neq b$, $1 \le a, b \le n$, $1 \le d \le 10^4$.

Notes

This problem is translated from the Croatian Open Competition in Informatics 2008/2009 Contest #3 T6 NAJKRACI.

见题面 Input 部分

见题面 Output 部分