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

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

A path from to is a shortest path if there is no other path from to that is shorter in length. Your task is to, for each road, output how many different shortest paths containing that road, modulo .

#### Input Specification

The first line contains two integers and , the number of cities and roads.

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

#### Output Specification

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

#### Scoring

In test cases worth of points, will be at most and will be at most .

In test cases worth of points, will be at most and will be at most .

#### 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
```

## Comments

Just want to clarify sample case 3, there are two edges from 4 to 2 with the same cost 3. That's why the edge <1, 3> with cost 2 is used in 4 different shortest paths: 1) path from 1 to 3, 2) path from 1 to 4, 3) path from 1 to 2 and 4) path from 1 to 2.