题目描述

给定一个连通的带边权的图（允许自环和重边），求不同的最小生成树个数。两个生成树不同当它们所用的边的序号不同，换句话说，重边算多次。

输入格式

第一行 $n$，$m$，表示点数和边数。

下接 $m$ 行，每行 $3$ 个数 $k_1$，$k_2$，$w$，表示 $k_1$ 和 $k_2$ 之间有一条权值为 $w$ 的边。

输出格式

仅一行一个数：生成树个数 ans，输出 $ans \mod 1000003$ 的值。

样例输入

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

样例输出

5

样例解释：

$5$ 棵生成树分别如下（边按输入顺序标号）：

$(1,3)$ ， $(2,3)$ ， $(1,4)$ ， $(2,4)$ ， $(3,4)$。

$5$ 号边是自环。

数据规模及约定

不会存在 $5$ 条及 $5$ 条以上的边，他们的边权是相同的。

对于 $100 \%$ 的数据： $1\le n\le 5\times 10^4$，$1\le m\le 10^5$。

题目来源

HNOI2009 集训 Day3