摧毁

题目描述

我们有一个由 $N$ 个顶点和 $M$ 条边组成的连通无向图。

顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。边 $i$ 连接顶点 $A_i$ 和顶点 $B_i$。

高桥君将从这个图中删去零条或多条边。

删除边 $i$ 时，如果 $C_i \geq 0$，则获得 $C_i$ 的奖励；如果 $C_i \lt 0$，则要支付 $|C_i|$ 的罚金。

请找出在删边之后图必须保持连通的前提下，高桥君能获得的最大总奖励。

输入格式

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

$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

可能存在重边和自环。

数据范围

• $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$
• 给定的图是连通的
• 输入中的值全部为整数