towerdefense

Ook the Oktopus is addicted to a new game -- Bloons Tower Defense. Ook wants to protect his castle from the bloons with his 3 amazing attacks: he can smash the bloons with his Oktopus legs, squirt ink at bloons to slow them down (bloons can't move if they can't see where they're going), or shoot at bloons with LaZ0r eyes. Between Ook's castle and the bloons' camp, there is some multidimensional hyperspace with N-2 nodes (numbered from 1 to N-2), and E hyperspace tunnels. The existence of a (1-directional) hyperspace tunnel between node A and B means that bloons need to travel some positive distance C to get from A to B if they use that tunnel. There could possibly be more than 1 tunnel joining any pair of nodes A and B. Ook's castle is at node N-1 and the bloons' camp is at node 0.

However, Ook is easily distracted. If the bloons move in too many directions at once, Ook will be distracted and unable to defend his castle from the bloons. Fortunately, Ook has spies all over the bloons camp and knows some insider information. From his uber-secret spying on bloons, Ook knows that bloons don't have legs and actually need quite a lot of air power to move. The bloons are quite lazy and will always take the shortest path possible between any two points.

Ook will like to know how many different paths the bloons can take from their camp to attack his castle so that he can defend it most effectively. However, Ook can't count because he is quite short-sighted. Can you help Ook?

Input

The first line contains 2 numbers, N and E.

The next E lines contain 3 numbers, A, B and C, which indicates there is a tunnel from A to B with distance C.

Output

Output 1 line with the number of ways mod 1000000007 the bloons can get from their camp to Ook's castle.

Constraints

For all subtasks, 1 < N ≤ 100,000, 1 ≤ E ≤ 500,000, 0 ≤ A,B ≤ N, 0 < C ≤ 1000.

Subtask 1 (7%): There is at most 1 tunnel starting from each node.

Subtask 2 (11%): 3 ≤ N ≤ 100,000. There are exactly N-2 tunnels starting from node 0, and exactly 1 tunnel ends at each node between nodes 1 to N-2. There is exactly 1 tunnel starting at each of the nodes numbered from 1 to N-2 and ending at node N-1.

Subtask 3 (29%): 1 < N ≤ 500.

Subtask 4 (17%): There are no cycles in the graph.

Subtask 5 (36%): No further constraints.

Sample Input

5 5
0 1 10
1 2 2
1 3 3
2 4 3
3 4 2

Sample Output

2

Explanation: there are 2 possible ways for the bloons to go from 0 to 4. (0 → 1 → 2 → 4 and 0 → 1 → 3 → 4)