给定一个N个点M条边的有向图。（点的编号从1到N）每条边上有权，表示边连接的两点间的距离（注意是有向边）。A点到B点的路径的长度为所经过的所有边的权值之和。A到B的最短路为所有路径中长度最小的一个。
你的工作是对于每条边，输出有多少条最短路经过它。（结果对1 000 000 007求余）
输入：
第一行两个整数 N和 M (1 ≤ N ≤ 1500, 1 ≤ M ≤ 5000), 表示点和边.
接下来M行，每行3个数O, D and L.表示点O到D的距离为L，O和D不相同且L不超过10000.
输出：
M行，每行一个整数，第i行表示对应输入的第i条边，经过它的最短路的条数对 1 000 000 007. 的余数。
注意；
30%的数据, N 不超过15且M不超过 30.
60%的数据， N 不超过300且M不超过1000.
输入：
4 3
1 2 5
2 3 5
3 4 5
输出：
3
4
3
输入：
4 4
1 2 5
2 3 5
3 4 5
1 4 8
输出：
2
3
2
1
输入：
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
输出：
0
4
6
6
6
7
2
6