Destruction

题目描述

我们有一个连通的无向图，包含 $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 能获得的最大总奖励。

输入格式

输入从标准输入按以下格式给出： $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

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

1

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$ 给定的图是连通的。 输入中的所有数值均为整数。删除边 $4$ 和 $5$ 可得到总奖励 $4$。你不能得到更多，所以答案是 $4$。
删除时可能会有得到负奖励的边。
图中可能存在重边和自环。

标签: AtCoder|abc218E

来源

AtCoder|abc218E