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

我们称道路 $F$ 是道路 $E$ 的延续，如果道路 $E$ 的终点城市与道路 $F$ 的起点城市相同。从城市 $A$ 到城市 $B$ 的路径是一个道路序列，使得第一条道路的起点是城市 $A$，其余每条道路都是前一条道路的延续，且最后一条道路的终点是城市 $B$。路径的长度是其中所有道路长度的总和。

如果从 $A$ 到 $B$ 没有其他长度更短的路径，则从 $A$ 到 $B$ 的路径是一条最短路径。

你的任务是，对于每条道路，输出有多少条不同的最短路径包含该道路，结果对 $1\,000\,000\,007$ 取模。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 1500$，$1 \le M \le 5000$），分别表示城市和道路的数量。

接下来的 $M$ 行，每行包含三个正整数 $O$、$D$ 和 $L$。这表示一条从城市 $O$ 到城市 $D$ 且长度为 $L$ 的单向道路。$O$ 和 $D$ 不相同，且 $L$ 最多为 $10000$。

输出格式

输出 $M$ 行，每行一个整数——对于每条道路，输出包含该道路的不同最短路径的数量对 $1\,000\,000\,007$ 取模后的结果。输出的顺序应当与输入中道路的顺序一致。

子任务

• 在占总分 $30\%$ 的测试数据中，$N$ 最多为 $15$，$M$ 最多为 $30$。
• 在占总分 $60\%$ 的测试数据中，$N$ 最多为 $300$，$M$ 最多为 $1000$。

样例

输入 1

4 3
1 2 5
2 3 5
3 4 5

输出 1

3
4
3

输入 2

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

输出 2

2
3
2
1

输入 3

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

0
4
6
6
6
7
2
6