A Walk Through The Forest
Jimmy experiences a lot of stress at work these days, especially since his accident made working difficult. To relax after a hard day, he likes to walk home. To make things even nicer, his office is on one side of a forest, and his house is on the other. A nice walk through the forest, seeing the birds and chipmunks is quite enjoyable.
The forest is beautiful, and Jimmy wants to take a different route everyday. He also wants to get home before dark, so he always takes a path to make progress towards his house. He considers taking a path from $A$ to $B$ to be progress if there exists a route from $B$ to his home that is shorter than any possible route from $A$. Calculate how many different routes through the forest Jimmy might take.
Input contains several test cases (at most $10$) followed by a line containing $0$. Jimmy has numbered each intersection or joining of paths starting with $1$. His office is numbered $1$, and his house is numbered $2$. The first line of each test case gives the number of intersections $N$, $1 < N \le 1000$, and the number of paths $M$. The following $M$ lines each contain a pair of intersections $a, b$ and an integer distance $1 \le d \le 1000000$ indicating a path of length $d$ between intersection $a$ and a different intersection $b$. Jimmy may walk a path any direction he chooses. There is at most one direct path between any pair of intersections.
For each test case, output a single integer indicating the number of different routes through the forest. You may assume that this number does not exceed $2147483647$.
|Sample Input 1||Sample Output 1|
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