숲을 지나는 산책

지미는 요즘 직장에서 스트레스를 많이 받고 있습니다. 특히 사고 이후로 일하기가 더 힘들어졌습니다. 힘든 하루를 마치고 긴장을 풀기 위해 지미는 걸어서 집에 가는 것을 좋아합니다. 다행히 그의 사무실은 숲의 한쪽에, 집은 반대쪽에 있어서 새와 다람쥐를 구경하며 숲을 가로질러 걷는 즐거운 산책을 할 수 있습니다.

숲이 아름답기 때문에 지미는 매일 서로 다른 경로로 걷고 싶어 합니다. 또한 어두워지기 전에 집에 도착하고 싶어서, 항상 집을 향해 진전이 있는 길만 걷습니다.

구체적으로, 교차로 $A$에서 교차로 $B$로 가는 길은 $B$에서 집까지의 최단 거리가 $A$에서 집까지의 최단 거리보다 엄격하게 짧을 때에만 진전으로 인정됩니다. 지미가 사무실에서 집까지 갈 수 있는 서로 다른 경로가 몇 가지인지 구하세요.

입력은 여러 개의 테스트 케이스로 이루어지며, 마지막에 $0$ 하나만 있는 줄이 옵니다.

길이 만나는 각 교차로에는 $1$번부터 번호가 매겨져 있습니다. 지미의 사무실은 $1$번 교차로이고, 그의 집은 $2$번 교차로입니다.

각 테스트 케이스의 첫 줄에는 교차로의 수 $N$ ($1 < N \le 1000$)과 길의 수 $M$이 주어집니다. 이어지는 $M$개의 줄에는 각각 서로 다른 두 교차로 $a$, $b$와 정수 거리 $d$ ($1 \le d \le 1000000$)가 주어지며, 이는 교차로 $a$와 $b$ 사이에 길이가 $d$인 길이 있음을 의미합니다. 지미는 어떤 길이든 원하는 방향으로 걸을 수 있으며, 임의의 두 교차로 사이에는 최대 하나의 길만 존재합니다.

각 테스트 케이스마다 숲을 지나는 서로 다른 경로의 수를 정수 하나로 출력하세요. 이 수는 $2147483647$을 넘지 않는다고 가정해도 됩니다.