NAJKRACI  Najkraci
A road network in a country consists of N cities and M oneway roads. The cities are numbered 1 through N. For each road we know the origin and destination cities, as well as its length.
We say that the road F is a continuation of road E if the destination city of road E is the same as the origin city of road F. A path from city A to city B is a sequence of road such that origin of the first road is city A, each other road is a continuation of the one before it, and the destination of the last road is city B. The length of the path is the sum of lengths of all roads in it.
A path from A to B is a shortest path if there is no other path from A to B that is shorter in length.
Your task is to, for each road, output how many different shortest paths containing that road, modulo 1 000 000 007.
Input
The first line contains two integers N and M (1 ≤ N ≤ 1500, 1 ≤ M ≤ 5000), the number of cities and roads.
Each of the following M lines contains three positive integers O, D and L. These represent a oneway road from city O to city D of length L. The numbers O and D will be different and L will be at most 10000.
Output
Output M integers, each on its own line – for each road, the number of different shortest paths containing it, modulo 1 000 000 007. The order of these numbers should match the order of roads in the input.
Example
Input: 4 4 1 2 5 2 3 5 3 4 5 1 4 8 Output: 2 3 2 1 Input: 5 8 1 2 20 1 3 2 2 3 2 4 2 3 4 2 3 3 4 5 4 3 5 5 4 20 Output: 0 4 6 6 6 7 2 6
Note: The test data for this problem consist of the official test cases from the contest, as well some cases of my own.
hide comments
sharjeel_spoj:
20201112 10:09:38
Floyd warshall will not work with this time limit. Use dijkstra and dfs. 

narek:
20180107 12:19:54
same as @Medo :(


xxbloodysantaxx:
20160709 11:02:38
My Dirty way to get an AC. :D


Medo:
20160611 02:43:42
My solution gives the same output as all all official test cases, but gets a wrong answer here....Are you sure your added test cases are correct ? Last edit: 20160611 02:43:57 

Deepak:
20150625 21:22:58
amazing problem.. 

Raghavendran Ramachandran:
20121129 19:00:10
The sample test cases provided are really good. They provide clarity regarding many questions. For one, the given graph may be a multigraph (which isn't immediately apparent from the problem description). 

Hussain Kara Fallah:
20120805 01:11:38
PLEASE I have a problem

Added by:  Neal Wu 
Date:  20081217 
Time limit:  1s1.707s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  Croatian Open 08/09  Contest 3 