A Walk Through the Forest

Jimmy has been under a lot of stress at work lately, especially since an accident made working harder for him. To unwind after a long day, he likes to walk home. Even better, his office sits on one side of a forest and his house on the other, so his commute is a pleasant stroll among the birds and chipmunks.

The forest is beautiful, and Jimmy wants to take a different route every day. He also wants to reach home before dark, so he only ever walks along a path that makes progress toward his house.

Concretely, walking a path from intersection $A$ to intersection $B$ counts as progress if the shortest route from $B$ to his home is strictly shorter than the shortest route from $A$ to his home. Count how many different routes through the forest Jimmy might take from his office to his house.

The input contains several test cases, followed by a line containing a single $0$.

Every intersection (a point where paths meet) is numbered starting from $1$. Jimmy's office is intersection $1$ and his house is intersection $2$.

The first line of each test case contains the number of intersections $N$ ($1 < N \le 1000$) and the number of paths $M$. Each of the next $M$ lines contains two intersections $a$ and $b$ and an integer distance $d$ ($1 \le d \le 1000000$), describing a path of length $d$ between the two distinct intersections $a$ and $b$. Jimmy may walk any path in either direction, and there is at most one path between any pair of intersections.

For each test case, output a single integer: the number of different routes through the forest. You may assume this number does not exceed $2147483647$.