### COCI 2008/2009, Contest #3

## Task NAJKRACI

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

The first line contains two integers N and M (1 ≤ N ≤ 1500, 1 ≤ M ≤ 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 1,000,000,007. The order of these numbers should match the order of roads in the input.

### Examples

## Input4 3 1 2 5 2 3 5 3 4 5 ## Output3 4 3 |
## Input4 4 1 2 5 2 3 5 3 4 5 1 4 8 ## Output2 3 2 1 |
## Input5 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 ## Output0 4 6 6 6 7 2 6 |

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 5.00s

**Memory Limit:** 32M

**Added:** Dec 14, 2008

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...