#2750. [HAOI2012]Road

题目描述

C国有$n$座城市，城市之间通过$m$条单向道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多少条不同的最短路经过该道路。现在，这个任务交给了你。

输入格式

第一行包含两个正整数$n、m$。 接下来$m$行每行包含三个正整数$u、v、w$，表示有一条从$u$到$v$长度为w的道路

输出格式

输出应有$m$行，第$i$行包含一个数，代表经过第i条道路的最短路的数目对$1000000007$取模后的结果

样例

样例输入

4 4  
1 2 5  
2 3 5  
3 4 5  
1 4 8

样例输出

2  
3  
2  
1

数据范围与提示

数据规模

$30$%的数据满足：$n≤15、m≤30$；

$60$%的数据满足：$n≤300、m≤1000$；

$100$%的数据满足：$n≤1500、m≤5000、w≤10000$；