AT_abc218_e [ABC218E] Destruction

题目描述

有一个包含 $N$ 个顶点和 $M$ 条边的连通无向图。
顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$，第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

高桥君打算从这个图中移除 $0$ 条或多条边。

如果移除第 $i$ 条边，当 $C_i \geq 0$ 时可以获得 $C_i$ 的奖励，当 $C_i < 0$ 时需要支付 $|C_i|$ 的罚金。

在移除边之后，图必须仍然保持连通。请你求出高桥君能够获得的最大总奖励。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$

输出格式

请输出答案。

样例 1

输入

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

输出

4

样例 2

输入

3 3
1 2 1
2 3 0
3 1 -1

输出

1

样例 3

输入

2 3
1 2 -1
1 2 2
1 1 3

输出

5

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $N-1 \leq M \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$
• $-10^9 \leq C_i \leq 10^9$
• 给定的图是连通的
• 输入中的所有值均为整数

样例解释 1

通过移除第 $4,5$ 条边，可以获得总共 $4$ 的奖励。无法获得比这更多的奖励，因此答案为 $4$。

样例解释 2

也可能存在奖励为负数的边。

样例解释 3

也可能存在重边或自环。

由 ChatGPT 4.1 翻译