P6413 [COCI 2008/2009 #3] NAJKRACI

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.

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 $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.

#### 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](https://hsin.hr/coci/archive/2008_2009), [Contest #3](https://hsin.hr/coci/archive/2008_2009/contest3_tasks.pdf), T6 NAJKRACI. Translated by ChatGPT 5