Three friends Aakash, Sameer and Siddharth plan to go on a road trip. But they have a variety of options when it comes to the route they choose from their home city H (numbered 1) to the destination city D (numbered 2). In their route, they consider going from city A to city B only if the shortest distance from B to D is strictly less than A to D. Find out the total number of options they have.

Input Specification
Input contains several test cases followed by a line containing 0. The first line of each test case gives the number of cities N and the number of highways M, which connect two cities. The following M lines each contain a pair of cities a b and an integer distance d indicating a path of length d between cities a and b. They may drive through any highway. There is at most one highway between any pair of cities.

Output Specification
For each test case, output a single integer indicating the number of different routes from H to D modulus 109+7.

Constraints
Test cases < 15
2 <= N <= 1000
1 <= d <= 106

Sample Input``` 5 6 1 3 2 1 4 2 3 4 3 1 5 12 4 2 34 5 2 24 7 8 1 3 1 1 4 1 3 7 1 7 4 1 7 5 1 6 7 1 5 2 1 6 2 1 0```

Sample Output``` 2 4```

Explanation
Sample Case 1 : 1-4-2 and 1-5-2
Sample Case 2 : 1-3-7-5-2, 1-3-7-6-2, 1-4-7-5-2, 1-4-7-6-2

Problem Tester: Dhruva Bhaswar

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 10 Second(s)
Score: 0 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0