SP8980 KOICOST - Cost

给你一个含有 $N$ 个顶点和 $M$ 条边的无向图，图中的每条边都有一个唯一的权重。 定义一个函数 $Cost(u, v)$，具体过程如下： 当顶点 $u$ 和 $v$ 之间存在路径时，不断删除路径中权重最小的边，直到两点之间不再连通。$Cost(u, v)$ 是在这个过程中被删除的所有边的权重之和。 例如，在上图中（与样例输入相同），$Cost(2, 6) = 2+3+4+5+6 = 20$。 给定这个无向图，你需要计算所有顶点对 $(u, v)$ 满足 $u < v$ 的 $Cost(u, v)$ 的总和。由于结果可能非常大，需要将最终结果对 $10^9$ 取模后输出。

输入的第一行包含两个整数 $N$ 和 $M$，表示图的顶点数和边数。（$1 \le N \le 100,000$，$0 \le M \le 100,000$） 接下来的 $M$ 行中，每行包含三个整数 $u$, $v$ 和 $w$，表示顶点 $u$ 和 $v$ 之间有一条权重为 $w$ 的边。（$1 \le u, v \le N$，$1 \le w \le 100,000$）

输出所要求的总和对 $10^9$ 取模后的值。 这是题目规定的数据规模与限制条件： - 顶点数 $1 \le N \le 100,000$。 - 边数 $0 \le M \le 100,000$。 - 顶点编号 $1 \le u, v \le N$。 - 边权重 $1 \le w \le 100,000$。 **本翻译由 AI 自动生成**