Description

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

For each edge, compute (modulo $10^9+7$) how many times it is used by shortest paths between any pair of vertices.

If there are multiple shortest paths between vertices $A$ and $B$, then each shortest path is counted once. You can refer to the output of the 3rd and 4th edges in Sample 4 to understand this sentence.

Input Format

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

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

Output Format

Output $m$ lines.

Each line outputs one integer. The value on the $i$-th line represents (modulo $10^9+7$) the number of times the edge read on line $i+1$ is used by shortest paths between any pair of vertices.

4 3
1 2 5
2 3 5
3 4 5 

3
4
3 

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

2
3
2
1 

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 

0
4
6
6
6
7
2
6 

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

3
4
2
4

Hint

Constraints and Notes

• For $30\%$ of the testdata, $n \le 15$, $m \le 30$.
• For $60\%$ of the testdata, $n \le 300$, $m \le 10^3$.
• For $100\%$ of the testdata, $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$.

Explanation

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

Translated by ChatGPT 5