一个国家的道路网由N个城市和M条单向道路组成。城市编号为1到N。对于每条道路，我们知道起点和终点城市，以及其长度。

如果E路的目的地城市与F路的起点城市相同，我们说F路是E路的延续。从A市到B市的道路是一系列道路，第一条道路的起点是A市，另一条道路是前一条道路的延续，最后一条道路的终点是B市。道路的长度是其中所有道路长度的总和。

如果从A到B没有其他长度更短的路径，那么从A到B的路径就是最短路径。

对于每条道路，输出包含该道路的不同最短路径数，并模10000007

一个国家的道路网由N个城市和M条单向道路组成。城市编号为1到N。对于每条道路，我们知道起点和终点城市，以及其长度。

如果E路的目的地城市与F路的起点城市相同，我们说F路是E路的延续。从A市到B市的道路是一系列道路，第一条道路的起点是A市，另一条道路是前一条道路的延续，最后一条道路的终点是B市。道路的长度是其中所有道路长度的总和。

如果从A到B没有其他长度更短的路径，那么从A到B的路径就是最短路径。

对于每条道路，输出包含该道路的不同最短路径数，并模10000007。


### 输入格式:
第一行包含两个整数$$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:
in
4 3
1 2 5
2 3 5
3 4 5


### 输出样例1:
out
3
4
3


### 输入样例2:
in
4 4
1 2 5
2 3 5
3 4 5
1 4 8


### 输出样例2:
out
2
3
2
1


### 输入样例3:
in
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


### 输出样例3:
out
0
4
6
6
6
7
2
6






答案：若无答案欢迎评论