시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 50 10 10 21.277%

문제

도시 N개와 일방통행 도로 M개로 이루어진 도로 네트워크가 있다. 도시는 1번부터 N번까지 번호가 매겨져 있다. 또, 각 도로의 출발 도시와 도착 도시, 그리고 길이를 알고 있다.

도로 E의 도착 도시와 도로 F의 시작 도시가 같다면, 도로 F를 도로 E의 연장선이라고 한다. A에서 B로 가는 경로란 첫 도로의 시작 도시가 A이고 마지막 도로의 도착 도시가 B이면서 각 도로가 이전 도로의 연장선인 도로의 연속이다. 경로의 길이는 경로에 포함된 도로의 길이의 합이다.

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

각각의 도로에 대해서, 그 도로를 포함하는 최단 경로가 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

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

다음 M개 줄에는 도로의 정보를 나타내는 세 정수 O, D, L이 주어진다. 도로의 시작 도시가 O이고, 도착 도시가 D이면서 길이가 L인 도로라는 의미이다. O와 D는 다르고, L은 많아야 10000이다.

출력

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

예제 입력

4 3
1 2 5
2 3 5
3 4 5

예제 출력

3
4
3

힌트