执着的朝圣者

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

现在有n座城市,编号从1n,铁牌狗住在城市1,他心中的圣地位于城市n

又因为铁牌狗的心里住着一头攻城狮,所以他总是喜欢选择走最短路。由于铁牌狗实在太笨了,所以他想请你帮忙计算一下从城市1到城市n一共有多少条不同的最短路。

设有两条最短路A,B,如果存在一条边在A中而不在B中,那么我们就说AB是两条不同的最短路。

Input

 

多组输入。对于每组数据:

第一行输入两个整数nm2 <= n <= 10^5,1 <= m <= 300000) 。

接下来个m行,每行三个整数u,v,w(1 <= u ,v<= n,1 <= w <= 1000),表示有一条边从城市u指向城市v(不能从vu),权值为

 

Output

 

输出一个整数,代表最短路的条数对1000000007取余后的结果。

 

Sample Input

3 2
1 2 10
2 3 10
3 3
1 2 10
2 3 11
2 3 100
3 3
1 2 10
2 3 10
2 3 10

Sample Output

1
1
2

Hint

 

Source

zmx