时间限制：1秒　　内存限制：256M

---

【题目描述】

　　Jimmy下班需要穿过一个森林。劳累一天后森林中漫步是件非常惬意的事，所以他打算每天沿着一条不同的路径回家，欣赏不同的风景。但他不想太晚回家，因此他不打算走“回头路”。换句话说，他只沿着满足如下条件的道路 \((A,B)\) 走：存在一条从 \(B\) 出发回家的路径比所有从 \(A\) 出发回家的路径都短。

　　你的任务是计算一共有多少条不同的回家路径。

【输入格式】

　　第一行为 \(n,m\)，交叉点的数目和道路的数目。交叉点编号为 \(1..n\)，公司编号为 1，家编号为 2。
　　以下 \(m\) 行每行 3 个整数：\(a,b,d（1≤d≤1000000）\)，表示有一条连接 \(a\) 和 \(b\) 的双向道路，长度为 \(d\)。

【输出格式】

　　输出路径条数。这个数可能很大，请输出 mod 20080814 的结果。

【输入输出样例】

　Input

5 6
1 3 2
1 4 2
3 4 3
1 5 12
4 2 34
5 2 24

　Output

2
10
-1

【数据限制】

　　对于 \(100\%\) 的数据，\(1 < n ≤ 1000\)。

【来源】

　　Mr.he