问题描述

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

高桥要从这个图中移除零条或多条边。

当移除第 $i$ 条边时，如果 $C_i \\geq 0$，将获得奖励 $C_i$，如果 $C_i<0$，将受到罚款 $|C_i|$。

求在移除边后图必须保持连通的情况下，高桥能够获得的最大总奖励。

约束条件

• $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$

输出

输出答案。

示例输入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

可能存在重边和自环。