시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 144 29 25 26.596%

문제

도시 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로 나눈 나머지를 한 줄에 하나씩 출력한다. 출력은 입력으로 주어진 도로 순서대로 해야 한다.

예제 입력 1

4 3
1 2 5
2 3 5
3 4 5

예제 출력 1

3
4
3

힌트

W3sicHJvYmxlbV9pZCI6IjI5NTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWI4NWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0XHViM2M0XHVjMmRjIE5cdWFjMWNcdWM2NDAgXHVjNzdjXHViYzI5XHVkMWI1XHVkNTg5IFx1YjNjNFx1Yjg1YyBNXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIzYzRcdWI4NWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHViM2M0XHVjMmRjXHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWFjMDEgXHViM2M0XHViODVjXHVjNzU4IFx1Y2Q5Y1x1YmMxYyBcdWIzYzRcdWMyZGNcdWM2NDAgXHViM2M0XHVjYzI5IFx1YjNjNFx1YzJkYywgXHVhZGY4XHViOWFjXHVhY2UwIFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIzYzRcdWI4NWMgRVx1Yzc1OCBcdWIzYzRcdWNjMjkgXHViM2M0XHVjMmRjXHVjNjQwIFx1YjNjNFx1Yjg1YyBGXHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWIzYzRcdWMyZGNcdWFjMDAgXHVhYzE5XHViMmU0XHViYTc0LCBcdWIzYzRcdWI4NWMgRlx1Yjk3YyBcdWIzYzRcdWI4NWMgRVx1Yzc1OCBcdWM1ZjBcdWM3YTVcdWMxMjBcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yjc4MCBcdWNjYWIgXHViM2M0XHViODVjXHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWIzYzRcdWMyZGNcdWFjMDAgQVx1Yzc3NFx1YWNlMCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViM2M0XHViODVjXHVjNzU4IFx1YjNjNFx1Y2MyOSBcdWIzYzRcdWMyZGNcdWFjMDAgQlx1Yzc3NFx1YmE3NFx1YzExYyBcdWFjMDEgXHViM2M0XHViODVjXHVhYzAwIFx1Yzc3NFx1YzgwNCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjNWYwXHVjN2E1XHVjMTIwXHVjNzc4IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWM3NzRcdWIyZTQuIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVhY2JkXHViODVjXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0QVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwMFx1YjI5NCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViMjk0IEFcdWM1ZDBcdWMxMWMgQlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjIFx1YzkxMVx1YzVkMFx1YzExYyBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjODNcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMDFcdWFjMDFcdWM3NTggXHViM2M0XHViODVjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhZGY4IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWJhODcgXHVhYzFjIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxNTAwLCAxICZsZTsgTSAmbGU7IDUwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IE8sIEQsIExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMmRjXHVjNzkxIFx1YjNjNFx1YzJkY1x1YWMwMCBPXHVjNzc0XHVhY2UwLCBcdWIzYzRcdWNjMjkgXHViM2M0XHVjMmRjXHVhYzAwIERcdWM3NzRcdWJhNzRcdWMxMWMgXHVhZTM4XHVjNzc0XHVhYzAwIExcdWM3NzggXHViM2M0XHViODVjXHViNzdjXHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gT1x1YzY0MCBEXHViMjk0IFx1YjJlNFx1Yjk3NFx1YWNlMCwgTFx1Yzc0MCBcdWI5Y2VcdWM1NDRcdWM1N2MgMTAwMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjZDFkIE1cdWFjMWMgXHViM2M0XHViODVjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWFkZjggXHViM2M0XHViODVjXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWM3NDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWIzYzRcdWI4NWMgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjk1OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5BSktSQUNJIiwiZGVzY3JpcHRpb24iOiI8cD5BIHJvYWQgbmV0d29yayBpbiBhIGNvdW50cnkgY29uc2lzdHMgb2YgTiBjaXRpZXMgYW5kIE0gb25lLXdheSByb2Fkcy4gVGhlIGNpdGllcyBhcmUgbnVtYmVyZWQgMSB0aHJvdWdoIE4uIEZvciBlYWNoIHJvYWQgd2Uga25vdyB0aGUgb3JpZ2luIGFuZCBkZXN0aW5hdGlvbiBjaXRpZXMsIGFzIHdlbGwgYXMgaXRzIGxlbmd0aC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Ugc2F5IHRoYXQgdGhlIHJvYWQgRiBpcyBhIGNvbnRpbnVhdGlvbiBvZiByb2FkIEUgaWYgdGhlIGRlc3RpbmF0aW9uIGNpdHkgb2Ygcm9hZCBFIGlzIHRoZSBzYW1lIGFzIHRoZSBvcmlnaW4gY2l0eSBvZiByb2FkIEYuIEEgcGF0aCBmcm9tIGNpdHkgQSB0byBjaXR5IEIgaXMgYSBzZXF1ZW5jZSBvZiByb2FkIHN1Y2ggdGhhdCBvcmlnaW4gb2YgdGhlIGZpcnN0IHJvYWQgaXMgY2l0eSBBLCBlYWNoIG90aGVyIHJvYWQgaXMgYSBjb250aW51YXRpb24gb2YgdGhlIG9uZSBiZWZvcmUgaXQsIGFuZCB0aGUgZGVzdGluYXRpb24gb2YgdGhlIGxhc3Qgcm9hZCBpcyBjaXR5IEIuIFRoZSBsZW5ndGggb2YgdGhlIHBhdGggaXMgdGhlIHN1bSBvZiBsZW5ndGhzIG9mIGFsbCByb2FkcyBpbiBpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBwYXRoIGZyb20gQSB0byBCIGlzIGEgc2hvcnRlc3QgcGF0aCBpZiB0aGVyZSBpcyBubyBvdGhlciBwYXRoIGZyb20gQSB0byBCIHRoYXQgaXMgc2hvcnRlciBpbiBsZW5ndGguJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0bywgZm9yIGVhY2ggcm9hZCwgb3V0cHV0IGhvdyBtYW55IGRpZmZlcmVudCBzaG9ydGVzdCBwYXRocyBjb250YWluaW5nIHRoYXQgcm9hZCwgbW9kdWxvIDEgMDAwIDAwMCAwMDcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTSAoMSAmbGU7IE4gJmxlOyAxNTAwLCAxICZsZTsgTSAmbGU7IDUwMDApLCB0aGUgbnVtYmVyIG9mIGNpdGllcyBhbmQgcm9hZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIHRocmVlIHBvc2l0aXZlIGludGVnZXJzIE8sIEQgYW5kIEwuIFRoZXNlIHJlcHJlc2VudCBhIG9uZS13YXkgcm9hZCBmcm9tIGNpdHkgTyB0byBjaXR5IEQgb2YgbGVuZ3RoIEwuIFRoZSBudW1iZXJzIE8gYW5kIEQgd2lsbCBiZSBkaWZmZXJlbnQgYW5kIEwgd2lsbCBiZSBhdCBtb3N0IDEwMDAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBNIGludGVnZXJzIGVhY2ggb24gaXRzIG93biBsaW5lICZuZGFzaDsgZm9yIGVhY2ggcm9hZCwgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgc2hvcnRlc3QgcGF0aHMgY29udGFpbmluZyBpdCwgbW9kdWxvIDEgMDAwIDAwMCAwMDcuIFRoZSBvcmRlciBvZiB0aGVzZSBudW1iZXJzIHNob3VsZCBtYXRjaCB0aGUgb3JkZXIgb2Ygcm9hZHMgaW4gdGhlIGlucHV0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==