E - Destruction

分数：$500$ 分

问题描述

我们有一个由 $N$ 个顶点和 $M$ 条边组成的连通无向图。
顶点从 $1$ 编号到 $N$，边从 $1$ 编号到 $M$。第 $i$ 条边连接两个顶点 $A_i$ 和 $B_i$。

Takahashi 将要从这个图中移除零条或多条边。

移除第 $i$ 条边时，如果 $C_i \geq 0$，将获得 $C_i$ 的奖励；如果 $C_i<0$，将承担 $|C_i|$ 的惩罚。

求当图在移除边后保持连通的情况下，Takahashi 可以获得的最大总奖励。

约束

• $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$
• 所给图是连通的。
• 输入中的所有值都为整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_M$ $B_M$ $C_M$

输出

输出答案。

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

4

移除边 $4$ 和 $5$ 的总奖励为 $4$。无法获得更多奖励，所以答案为 $4$。

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

1

有些边在移除时可能会得到负奖励。

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

5

图中可能存在重边和自环。