该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

求最小生成树已经难不倒你了。

那么最小生成树的个数统计呢？

N 个点，编号为 1 ~ N。M条无向边。可能有自环，可能有重边。

问：该图有多少个不同的最小生成树？

注：两个最小生成树不同，当前仅当存在一条边不同时出现在这两个最小生成树中。

答案可能很大，你需要将其 mod 1000003 后输出。

输入格式

第一行：两个整数 N, M

接下来 M 行：每行三个整数：u, v, w，表示点 u 和点 v 之间有一条权值为 w 的无向边。

注：本题数据保证具有相同权值的边不会超过 5 条。

输出格式

一个整数，表示答案 mod 1000003

样例输入

3 5
1 2 6
1 2 6
2 3 6
3 1 6
3 3 8

样例输出

5

提示

100% 的数据：1 <= N <= 50000; 1 <= M <= 100000; 1 <= u, v <= N; 1 <= w <= 10^9