Problem1065--「一本通 3.1 例 1」黑暗城堡

1065: 「一本通 3.1 例 1」黑暗城堡

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 1  Solved: 1
Submit Status Web Board

Creator:

Description

你知道黑暗城堡有 NNN 个房间,MMM 条可以制造的双向通道,以及每条通道的长度。

城堡是树形的并且满足下面的条件:

DiD_iDi 为如果所有的通道都被修建,第 iii 号房间与第 111 号房间的最短路径长度;

SiS_iSi 为实际修建的树形城堡中第 iii 号房间与第 111 号房间的路径长度;

要求对于所有整数 iii (1≤i≤N1\le i\le N1iN),有 Si=DiS_i= D_iSi=Di 成立。

你想知道有多少种不同的城堡修建方案。当然,你只需要输出答案对 231−12^{31} -12311 取模之后的结果就行了。


Input

第一行为两个由空格隔开的整数 N,MN, MN,M;

第二行到第 M+1M+1M+1 行为 333 个由空格隔开的整数 x,y,lx, y, lx,y,l:表示 xxx 号房间与 yyy 号房间之间的通道长度为 lll


Output

一个整数:不同的城堡修建方案数对 231−12^{31} -12311 取模之后的结果。


Sample Input

4 6
1 2 1
1 3 2
1 4 3
2 3 1
2 4 2
3 4 1

Sample Output

6

HINT

对于全部数据,1≤N≤1000 1\le N\le 1000 1N10001≤M≤N(N−1)2 1\le M\le \frac{N(N-1)}{2} 1M2N(N1)1≤l≤2001\le l\le 2001l200


Source/Category


Submit Status