题目描述

在西游记的取经路上，唐僧、孙悟空、猪八戒和沙僧来到了一个神秘的山谷。山谷中有 N 个仙洞，仙洞之间有 M 条可以开辟的双向通道，每条通道都有固定的长度。为了方便行走，唐僧希望能找到一种通道开辟的方案，使得每个仙洞到大本营（即第 1 号仙洞）的路径最短。
山谷中的仙洞布局类似于一棵树，并且需要满足以下条件：
设 Di 为如果所有的通道都被开辟，第 i 号仙洞与第 1 号仙洞的最短路径长度；
而 Si 为实际开辟的树形山谷中第 i 号仙洞与第 1 号仙洞的路径长度；
要求对于所有整数 i (1 ≤ i ≤ N)，有 Si = Di 成立。
请计算有多少种不同的仙洞通道开辟方案，结果对 2^31−1 取模。

输入格式

第一行包含两个由空格隔开的整数 N 和 M；
接下来的 M 行，每行包含三个由空格隔开的整数 x, y, l，表示 x 号仙洞与 y 号仙洞之间的通道长度为 l。

输出格式

一个整数，表示不同的仙洞通道开辟方案数对 2^31−1 取模之后的结果。

样例

input

5 7
1 2 3
1 3 4
1 4 2
2 5 3
3 4 1
4 5 2
3 5 4

output

5

一共有 5 个仙洞，7 条通道，其中 1 号和 2 号，1 号和 3 号，1 号和 4 号，2 号和 5 号，3 号和 4 号，4 号和 5 号，3 号和 5 号仙洞之间的通道长度分别为 3，4，2，3，1，2，4。
而不同的仙洞通道开辟方案数对 2^31−1 取模之后的结果为 5。

数据范围与提示

对于全部数据，$ 1\le N\le 1000 $，$ 1\le M\le \frac{N(N-1)}{2} $，$1\le l\le 200$。