A road network in a country consists of $N$ cities and $M$ one-way roads. The cities are numbered $1$ through $N$. For each road we know the origin and destination cities, as well as its length.

We say that the road $F$ is a continuation of road $E$ if the destination city of road $E$ is the same as the origin city of road $F$. A path from city $A$ to city $B$ is a sequence of road such that origin of the first road is city $A$, each other road is a continuation of the one before it, and the destination of the last road is city $B$. The length of the path is the sum of lengths of all roads in it.

A path from $A$ to $B$ is a shortest path if there is no other path from $A$ to $B$ that is shorter in length.

Your task is to, for each road, output how many different shortest paths contain that road, modulo $1000000007$.

-----Input-----
The first line contains two integers $N$ and $M$ $(1 \le N \le 1500, 1 \le M \le 5000)$, the number of cities and roads.

Each of the following $M$ lines contains three positive integers $O$, $D$ and $L$. These represent a one-way road from city $O$ to city $D$ of length $L$. The numbers $O$ and $D$ will be different and $L$ will be at most $10000$.

-----Output-----
Output $M$ integers each on its own line – for each road, the number of different shortest paths containing it, modulo $1000000007$. The order of these numbers should match the order of roads in the input.

-----Examples-----
Sample Input 1:
4 3
1 2 5
2 3 5
3 4 5
Sample Output 1:
3
4
3

Sample Input 2:
4 4
1 2 5
2 3 5
3 4 5
1 4 8
Sample Output 2:
2
3
2
1

见题面

见题面