J12 实践-2 伪森林

题目描述

在图论中，伪森林是一个无向图，其中每个连通块最多只有一个环。$G$ 的最大伪森林是 $G$ 的伪森林子图，它不包含在 $G$ 的任何更大的伪森林中。一个伪森林比另一个大，当且仅当边的总价值大于另一个的价值。

输入格式

输入由多个测试案例组成。每个测试案例的第一行包含两个整数，$n$，$m$，它们是顶点的数量和边的数量。接下来的 $m$ 行，每行由三个整数组成，$u$，$v$，$c$，这意味着在u和v之间有一条值为 $c$ 的边，你可以假设没有自环，也没有重边。 最后一个测试案例后面是包含两个零的一行，这意味着输入的结束。

输出格式

输出最大伪森林子图的价值。

样例输入1

3 3
0 1 1
1 2 1
2 0 1
4 5
0 1 1
1 2 1
2 3 1
3 0 1
0 2 2
0 0

样例输出1

3
5

样例解析

第一组样例只有一个伪森林子图，边权和为 $3$。第二组样例有两个伪森林子图，但边权和最大的 $5$。

数据范围

对于 $100 \%$ 的数据：$0 < n \le 10000$，$0 \le m \le 100000$, $0 \lt c \le 10000$。