题目描述

吉米最近工作压力很大，尤其是在他的事故后工作变得更加困难。为了在辛苦的一天后放松，他喜欢步行回家。更棒的是，他的办公室位于一片森林的一侧，而他的家在另一侧。漫步穿过森林，欣赏鸟儿和花栗鼠的景色十分惬意。

吉米希望每天走一条不同的路线回家。他还希望在天黑前到家，因此总是选择能让他更“进步”的路径。他认为从路口$A$到路口$B$的路径是“进步的”，当且仅当存在一条从$B$到家的路线，其长度比任何从$A$到家的路线都短。请计算吉米从办公室到家可能的不同“进步”路径数量。

输入

输入包含多个测试用例，最后一行以$0$结束。吉米将每个路口（路径的交汇点）从$1$开始编号，他的办公室编号为$1$，家编号为$2$。

每个测试用例的第一行包含两个整数：路口数量$N$（$1 < N \leq 1000$）和路径数量$M$。接下来的$M$行每行包含三个整数$a$、$b$和距离$d$（$1 \leq d \leq 1000000$），表示路口$a$和$b$之间存在一条长度为$d$的双向路径。任意两个路口之间最多存在一条路径。

输出

对于每个测试用例，输出一个整数，表示吉米从办公室（路口$1$）到家（路口$2$）可能的不同“进步”路径数量。你可以假设这个数量不超过$2147483647$。

输入数据示例 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  

输出数据示例 1

2  
4  

来源

Waterloo 本地赛 2005.09.24