레이팅 미적용어떤 나라의 도로망은 \(N\)개의 도시와 \(M\)개의 일방통행 도로로 이루어져 있다. 도시에는 \(1\)부터 \(N\)까지 번호가 붙어 있다. 각 도로에 대해 출발 도시와 도착 도시, 그리고 길이를 알고 있다.
도로 \(E\)의 도착 도시가 도로 \(F\)의 출발 도시와 같으면, 도로 \(F\)는 도로 \(E\)의 연속이라고 한다. 도시 \(A\)에서 도시 \(B\)로 가는 경로란, 첫 도로의 출발지가 도시 \(A\)이고 나머지 각 도로가 바로 앞 도로의 연속이며 마지막 도로의 도착지가 도시 \(B\)인 도로들의 나열이다. 경로의 길이는 경로에 포함된 모든 도로의 길이의 합이다.
\(A\)에서 \(B\)로 가는 어떤 경로에 대해, \(A\)에서 \(B\)로 가는 더 짧은 다른 경로가 없으면 그 경로를 최단 경로라고 한다.
각 도로에 대해, 그 도로를 포함하는 서로 다른 최단 경로가 몇 개인지 \(1\,000\,000\,007\)로 나눈 나머지를 출력하는 것이 여러분의 과제이다.
첫째 줄에 두 정수 \(N\)과 \(M\) (\(1 \le N \le 1500\), \(1 \le M \le 5000\))이 주어진다. 도시와 도로의 개수이다.
다음 \(M\)개의 줄에는 세 양의 정수 \(O\), \(D\), \(L\)이 주어진다. 도시 \(O\)에서 도시 \(D\)로 가는 길이 \(L\)의 일방통행 도로를 나타낸다. \(O\)와 \(D\)는 서로 다르며 \(L\)은 최대 \(10000\)이다.
\(M\)개의 정수를 한 줄에 하나씩 출력한다. 각 도로에 대해, 그 도로를 포함하는 서로 다른 최단 경로의 개수를 \(1\,000\,000\,007\)로 나눈 나머지이다. 수의 순서는 입력에서 도로가 주어진 순서와 일치해야 한다.
채점: 전체 점수의 \(30\%\)에 해당하는 테스트 케이스에서는 \(N\)이 최대 \(15\), \(M\)이 최대 \(30\)이다. 전체 점수의 \(60\%\)에 해당하는 테스트 케이스에서는 \(N\)이 최대 \(300\), \(M\)이 최대 \(1000\)이다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 130점 |
4 3
1 2 5
2 3 5
3 4 53
4
34 4
1 2 5
2 3 5
3 4 5
1 4 82
3
2
15 8
1 2 20
1 3 2
2 3 2
4 2 3
4 2 3
3 4 5
4 3 5
5 4 200
4
6
6
6
7
2
6