Migrated from Lutece 2726 最小生成树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你一个 $n$ 个点 $m$ 条边的无向图，求最小生成树。

这是一个非常经典的问题，我们可以采用 kruskal, prim 等算法进行求解

现在你学会了如何算最小生成树，那么来计算下最小生成树的个数吧。

Input

第一行输入两个整数 $n,m\ (1\le n\le 100,1\le m\le 1000)$

接下来 $m$ 行每行三个数 $u,v,w\ (1\le u,v\le n,1\le w\le 10)$，表示一条边的两个端点和这条边的边权

Output

输出一个数，表示最小生成树个数对 $10000$ 取模。

Samples

5 10
2 5 3
2 4 2
3 1 3
3 4 2
1 2 3
5 4 3
5 1 3
4 1 1
5 3 3
3 2 3

4

Note

注意模数，数据保证无重边和自环

Resources

2022 UESTC ICPC Training for Graph