题目描述

NJ 市的快速发展得益于其便捷的交通。可是，随着经济的发展，大量的人进入 NJ 市， NJ 市的交通也承受着巨大的压力。现在， NJ 市正在筹划建设一个新型的交通枢纽，从而减轻交通的压力。

NJ 市包含 $n$ 个区，有些区之间有双向的干道存在。新型交通枢纽建设在这些干道的基础上，将其中的部分干道改进为新型干道。改进后，干道能承受的压力可以比原来增加几十倍。为了和谐发展，在新型的交通枢纽建成后，要求任何两个区之间都可以只通过新型干道（直接或间接地）连接。政府已经预测出每条干道改进为新型干道的费用。政府希望建设新型交通枢纽的总费用最小，并以巨额奖金向市民征集方案。政府很快发现费用最小的方案不一定唯一，所以决定将奖金平分给每一种方案的第一个设计者，即如果一个人设计的费用是最小的而且前面没人和他设计出一模一样的方案，则他可获奖。

Js08 被奖金深深的吸引，准备设计一种方案。可是，他发现方案可能会很多，如果最后获奖者太多，巨额的资金分到每个人头上的也不会太多。所以他决定先算一下可行的方案数是多少。

输入格式

输入共 $m + 1$ 行。

输入的第一行包含两个数 $n, m$，分别表示该市有多少个区和有多少条干道。

接下来 $m$ 行，每行三个数 $a_i$、$b_i$、$c_i$，表示 $a_i$ 区和 $b_i$ 区之间有一条干道，如果改进需要 $c_i$ 的费用。

输出格式

输出费用最小的方案有多少种。由于答案可能很大，你只要输出方案数除以 $31011$ 的模即可。

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

8

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$1 \leq m \leq 1000$，$1 \leq a _ i, b _ i \leq n$，$1 \leq c _ i \leq 10 ^ 9$。