# Road Trip

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 10

^{9}+7.

**Constraints**

Test cases < 15

2 <= N <= 1000

1 <= d <= 10

^{6}

**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 Setter : Shikhar Sharad*

*Problem Tester: Dhruva Bhaswar*

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