도로 네트워크

시간 제한1초메모리 제한128 MB

요약

방향 그래프에서 모든 도시 쌍에 대한 최단 경로 중 각 도로가 포함되는 경로의 개수를 구해 1,000,000,007로 나눈 나머지를 출력합니다.

난이도: 어려움10점 중 8점
유형: 최단 경로, 그래프, 조합론
정답자: 아직 제출이 없습니다

문제

도시 N개와 일방통행 도로 M개로 이루어진 도로 네트워크가 있다. 도시는 1번부터 N번까지 번호가 매겨져 있으며, 각 도로에는 시작 도시, 도착 도시, 길이가 정해져 있다.

도로 E의 도착 도시와 도로 F의 시작 도시가 같으면 도로 F를 도로 E 뒤에 이어 갈 수 있다. 도시 A에서 도시 B로 가는 경로는 첫 도로의 시작 도시가 A이고 마지막 도로의 도착 도시가 B인 도로들의 연속이며, 서로 이웃한 두 도로는 이렇게 이어져야 한다. 경로의 길이는 그 경로에 포함된 모든 도로 길이의 합이다.

A에서 B로 가는 최단 경로는 A에서 B로 가는 경로 중 길이가 가장 짧은 경로이다.

각 도로마다, 그 도로를 포함하는 최단 경로의 개수를 구하시오.

입력

첫째 줄에 도시의 수 N과 도로의 수 M이 주어진다. (2 <= N <= 1500, 1 <= M <= 5000)

다음 M개 줄에는 도로의 정보를 나타내는 세 정수 O, D, L이 주어진다. 이는 시작 도시가 O, 도착 도시가 D, 길이가 L인 일방통행 도로를 뜻한다. O와 D는 서로 다르며, L은 10,000 이하의 자연수이다.

출력

입력으로 주어진 순서대로 M개 도로 각각에 대해, 그 도로를 포함하는 최단 경로의 개수를 한 줄에 하나씩 출력한다. 각 값은 1,000,000,007로 나눈 나머지로 출력한다.

예제3

예제 1
입력
```
4 3
1 2 5
2 3 5
3 4 5
```
예상 출력
```
3
4
3
```
예제 2
입력
```
4 4
1 2 5
2 3 5
3 4 5
1 4 8
```
예상 출력
```
2
3
2
1
```

예제 3

입력

예상 출력