Ciel and Tomya

All submissions for this problem are available.
Tomya is a girl. She loves Chef Ciel very much.
Today, too, Tomya is going to Ciel's restaurant.
Of course, Tomya would like to go to Ciel's restaurant as soon as possible.
Therefore Tomya uses one of the shortest paths from Tomya's house to Ciel's restaurant.
On the other hand, Tomya is boring now to use the same path many times.
So Tomya wants to know the number of shortest paths from Tomya's house to Ciel's restaurant.
Your task is to calculate the number under the following assumptions.
This town has N intersections and M two way roads.
The ith road connects from the A_{i}th intersection to the B_{i}th intersection, and its length is
C_{i}.
Tomya's house is in the 1st intersection, and Ciel's restaurant is in the Nth intersection.
Input
The first line contains an integer T, the number of test cases.
Then T test cases follow.
The first line of each test case contains 2 integers N, M.
Then next M lines contains 3 integers denoting A_{i}, B_{i} and C_{i}.
Output
For each test case, print the number of shortest paths from Tomya's house to Ciel's restaurant.
Constraints
1 ≤ T ≤ 10
2 ≤ N ≤ 10
1 ≤ M ≤ N ∙ (N – 1) / 2
1 ≤ A_{i}, B_{i} ≤ N
1 ≤ C_{i} ≤ 10
A_{i} ≠ B_{i}
If i ≠ j and A_{i} = A_{j}, then B_{i} ≠ B_{j}
There is at least one path from Tomya's house to Ciel's restaurant.
Sample Input
2 3 3 1 2 3 2 3 6 1 3 7 3 3 1 2 3 2 3 6 1 3 9
Sample Output
1 2
Explanations
In the first sample, only one shortest path exists, which is 13.
In the second sample, both paths 123 and 13 are the shortest paths.
Author:  laycurse 
Editorial  http://discuss.codechef.com/problems/CIELTOMY 
Tags  backtracking, cook24, laycurse, simple 
Date Added:  4072012 
Time Limit:  0.395522 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 