J12 实践-5 绿色城市

题目描述

为了保护大自然，喵星开展了绿色城市的环保项目，对城市间的高速公路进行优化调整。

喵星上共有 $N$ 个编号为 $1\sim N$ 的城市和 $M$ 条编号为 $1\sim M$ 的高速公路，其中第 $i$ 条高速公路连接着城市 $A_i$ 和 $B_i$ ，停用该条公路将增加 $C_i$ 点环保评分（$C_i$ 为负数时，将扣除对应的评分）。

环保司长小喵将在城市间连通性不改变的情况下，停用这 $M$ 条高速公路中的若干（或 $0$）条以获得最大的环保评分。请你设计程序协助小喵。

输入格式

共 $M+1$ 行： 第一行两个整数 $N,M$ ，依次表示城市的数量和高速公路的数量； 接下来的 $M$ 行每行三个整数 $A_i,B_i,C_i$ ，依次表示第 $i$ 条高速公路连通的两个城市编号，以及停用该高速公路获得/减少的环保评分。

输出格式

一行一个整数，输出不改变城市间连通性的情况下，最大的环保评分。

样例输入1

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

样例输出1

4

样例1解析

停用第 $4,5$ 条高速公路能获得最高的 $4$ 点环保评分。

样例输入2

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

样例输出2

5

数据范围

对于 $100 \%$ 的数据：$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$ ；保证给定的图是连通的。