3385: 小 W 计树

小 W 千辛万苦做出了数列题，突然发现小 M被困进了迷宫里。
迷宫是一个有 N(2≤N≤1000)个顶点M(N−1≤M≤N∗(N − 1)/2 ) 条边的无向连通图。
设 dist1[i]表示在这个无向连通图中， 顶点 i 到顶点 1 的最短距离。
为了解开迷宫，现在要求小 W 在这个图中删除M − (N − 1)条边，使得这个迷宫变成一
棵树。设 dist2[i]表示在这棵树中，顶点i到顶点1 的距离。
小 W 的任务是求出有多少种删除方案，使得对于任意的 i，满足 dist1[i]=dist2[i]。
快点帮助小 W 救出小M 吧！

第一行，两个整数， N， M，表示有 N 个顶点和 M 条边。
接下来有 M 行，每行有 3 个整数 x, y, len(1 ≤ x, y ≤ n, 1 ≤ len ≤ 100)，
表示顶点 x 和顶点 y 有一条长度为 len 的边。
数据保证不出现自环、重边。

  一行两个整数，表示满足条件的方案数 mod 2147483647 的答案。 

3 3 
1 2 2 
1 3 1 
2 3 1 

2