102184: [AtCoder]ABC218 E - Destruction

Problem Statement

We have a connected undirected graph with $N$ vertices and $M$ edges.
The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ connects Vertices $A_i$ and $B_i$.

Takahashi is going to remove zero or more edges from this graph.

When removing Edge $i$, a reward of $C_i$ is given if $C_i \geq 0$, and a fine of $|C_i|$ is incurred if $C_i<0$.

Find the maximum total reward that Takahashi can get when the graph must be connected after removing edges.

Constraints

• $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$
• The given graph is connected.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

4

Removing Edges $4$ and $5$ yields a total reward of $4$. You cannot get any more, so the answer is $4$.

Sample Input 2

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

Sample Output 2

1

There may be edges that give a negative reward when removed.

Sample Input 3

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

Sample Output 3

5

There may be multi-edges and self-loops.

问题描述

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

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

删除第 i 条边时，如果 C_i >= 0，则获得奖励 C_i；如果 C_i < 0，则罚款 |C_i|。

找出当图在删除边后仍保持连通时，Takahashi 能获得的最大总奖励。

限制条件

• 2 <= N <= 2*10^5
• N-1 <= M <= 2*10^5
• 1 <= A_i,B_i <= N
• -10^9 <= C_i <= 10^9
• 给定的图是连通的。
• 输入中的所有值都是整数。

输入

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

$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

样例输出 1

4

删除边 4 和 5 可以获得总奖励 4。你无法获得更多，所以答案是 4。

样例输入 2

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

样例输出 2

1

可能存在删除时获得负奖励的边。

样例输入 3

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

样例输出 3

5

可能存在多边和自环。