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 containing that road, modulo $1000000007$.

Input Specification

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 Specification

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.

Scoring

In test cases worth $30\mathrm{\%}$ of points, $N$ will be at most $15$ and $M$ will be at most $30$.

In test cases worth $60\mathrm{\%}$ of points, $N$ will be at most $300$ and $M$ will be at most $1000$.

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

Sample Input 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

Sample Output 3

0
4
6
6
6
7
2
6