All Submissions


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

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

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