B. 白云的旅行

白云开始了一段旅程。

旅途中一共有 个城市，编号为 到 ，城市之间有一些道路相连。其道路结构可以抽象为一棵仙人掌。如果一个无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

白云对这些城市间的每条道路都有一个喜爱度。一条路径的喜爱度是其上所有道路的喜爱度的乘积。

现在白云在 号城市准备出发。为了制定合理的路线，白云会时不时问白兔：“从 号城市出发不经过重复道路到达 号城市的所有路径喜爱度之和是多少？”

这可难倒了白兔，请你帮忙对于 求出相应答案。只需要输出答案对一个质数取模后的值。

第 行两个正整数 表示城市的个数和道路的条数。保证 。

接下来 行每行两个正整数 表示一条连接城市 和 的喜爱度为 的道路。

保证输入的图是一棵仙人掌，没有自环，但可能有重边。

输出 行，第 行包含一个整数表示 时的答案。

样例输入 1

11 11
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 1 1
2 7 10
3 8 20
4 9 30
5 10 40
6 11 50

样例输出 1

3
2
2
2
2
2
20
40
60
80
100

样例解释 1

注意，两条路径不同为它们经过的边数不同或存在一个满足 路径长度 的 使得这两条路径经过的第 条边不同。

长度为的路径也是合法路径，权值视为 。

对于所有数据，。

虽然我没有给 的范围，但是熟悉仙人掌的小朋友都知道对于仙人掌肯定满足 。