P1669 · Bad Cowtractors

题意概述

有 (N) 个牛棚，计划在它们之间铺设网络。你手中有 (M) 条可选的线路候选，每条线路连接两个牛棚，铺设需要一定费用 (C)。

贝茜想"报复"抠门的农夫——她要在不出现环的前提下，选若干条线路把所有牛棚连成一张网，并且让总费用尽可能大。 如果无论如何都无法把所有牛棚连通，则输出 (-1)。

等价表述：在给定的无向图上，若存在生成树，则求一棵总费用最大的生成树的费用；否则输出 (-1)。

输入格式

• 第 1 行：两个整数 (N, M)。
• 接下来的 (M) 行：每行三个整数 (u, v, C)，表示可在牛棚 (u) 与 (v) 之间铺设一条费用为 (C) 的线路。

输出格式

• 一行一个整数：能够把所有牛棚连通且无环的方案中，最大的总费用；若无法连通，输出 (-1)。

样例

输入

5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17

输出

42

说明/约束

• (2 \le N \le 10^3)
• (1 \le M \le 2 \times 10^4)
• (1 \le C \le 10^5)
• 线路无方向，同一对牛棚可能给出多条候选线路（按题目语义通常视为可并存的不同候选）。
• 选取的线路必须使整张网连通，且不出现环（即形成一棵树）。