Description

Country C has $n$ cities connected by $m$ directed roads. A path is called a shortest path if and only if there does not exist another path from its start to its end whose total length is smaller. Two shortest paths are different if and only if the sequences of roads they contain are different. We need to assess the importance of each road by counting how many different shortest paths pass through that road. Now, this task is given to you.

Input Format

The first line contains two positive integers $n, m$.

Each of the next $m$ lines contains three positive integers $u, v, w$, indicating there is a road from $u$ to $v$ with length $w$.

Output Format

Output $m$ lines. The $i$-th line contains one number: the number of shortest paths that pass through the $i$-th road, modulo $10^9+7$.

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

2
3
2
1

Hint

Constraints

$30\%$ of the testdata satisfies: $n \le 15, m \le 30$.

$60\%$ of the testdata satisfies: $n \le 300, m \le 1000$.

$100\%$ of the testdata satisfies: $n \le 1500, m \le 5000, 1 \le w \le 10000$.

Multiple edges may exist.

Translated by ChatGPT 5