rainbow来到了Freda的城堡。现在rainbow已经搞清楚Freda的城堡有N个房间，M 条可以建造的双向通道，以及每条通道的长度。 Freda已经把城堡修建成树形的；但是，为了尽量提高自己的移动效率，Freda一定会使得城堡满足下面的条件： 设Di 为 如果所有的双向通道都被修建，第i 号房间与第1 号房间的最短路径长度； 设Si 为实际修建的树形城堡中第i 号房间与第1 号房间的路径长度； 对于所有满足1≤i≤N 的整数i，有Si = Di。 Freda和rainbow在一起玩的时候总喜欢探究一些东西，这次它们想知道有多少种不同的城堡修建方案，保证方案数大于0。 于是在编年史的下一页上，applepi “被”发现了这个问题。由于applepi 还要忙着看编年史，所以这个任务就交给你了。你只需要输出答案对(2^31)–1取模之后的结果就行了。

第一行有两个整数N 和M。 之后 M 行，每行三个整数X，Y 和L，表示可以修建X 和Y 之间的一条长度为L 的通 道。

输出一个整数，表示答案对(2^31)–1取模之后的结果。

3 3
1 2 2
1 3 1
2 3 1

2

applepi捧着编年史,翻啊翻,发现了小猫rainbow的故事…… 这天，rainbow显得无聊，于是去找Freda玩……