도로 네트워크

도시 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로 나눈 나머지로 출력한다.