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 ~1\,000\,000\,007~.

Input Specification

The first line contains two integers ~N~ and ~M~ ~(1 \leq N \leq 1500, 1 \leq M \leq 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 ~10\,000~.

Output Specification

Output ~M~ integers each on its own line – for each road, the number of different shortest paths containing it, modulo ~1\,000\,000\,007~. The order of these numbers should match the order of roads in the input.

Scoring

In test cases worth ~30\%~ of points, ~N~ will be at most ~15~ and ~M~ will be at most ~30~.

In test cases worth ~60\%~ 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