题目描述

在顺利攻破Lord lsp的防线之后，lqr一行人来到了Lord lsp的城堡下方。

Lord lsp黑化之后虽然拥有了强大的超能力，能够用意念力制造建筑物，但是智商水平却没怎么增加。

现在lqr已经搞清楚黑暗城堡有$\red {N}$个房间，$\red {M}$条可以制造的双向通道，以及每条通道的长度。

lqr深知Lord lsp的想法，为了避免每次都要琢磨两个房间之间的最短路径，Lord lsp一定会把城堡修建成树形的。

但是，为了尽量提高自己的移动效率，Lord lsp一定会使得城堡满足下面的条件：

设 $\red {D[i]}$ 为如果所有的通道都被修建，第 $\red {i}$ 号房间与第$\red {1}$号房间的最短路径长度；而 $\red {S[i]}$ 为实际修建的树形城堡中第 $\red {i }$号房间与第$\red {1}$号房间的路径长度；要求对于所有整数 $\red {i}$，有 $\red {S[i]=D[i]}$ 成立。

为了打败Lord lsp，lqr想知道有多少种不同的城堡修建方案。

你需要输出答案对 $\red {2 ^{31} –1}$ 取模之后的结果。

输入格式

第一行有两个整数 $\red {N}$ 和 $\red {M}$。

之后 $\red {M }$行，每行三个整数$\red {X，Y }$和$\red {L}$，表示可以修建 $\red {X }$和 $\red {Y}$ 之间的一条长度为 $\red {L }$的通道。

输出格式

一个整数，表示答案对 $\red {2 ^{31} –1}$ 取模之后的结果。

样例

输入样例

3 3
1 2 2
1 3 1
2 3 1

输出样例

2

提示

$\red {2≤N≤1000}$,

$\red {N−1≤M≤N(N−1)/22}$,

$\red {1≤L≤100}$