#P1818. 2024.4.12-ELM-第三题-塔子哥删边

2024.4.12-ELM-第三题-塔子哥删边

题目描述

塔子哥拿到了一个无向图，她准备副除若干条边，使得最终怡好有2个连通块。塔子哥每次副除一条边后可以获得这条边边权的价值，现在塔子哥想知道自己能获得的最大价值是多少?

输入描述

第一行输入两个整数n,mn,m，代表节点数量和边的数量。

接下来的m行，每行输入个正整数山4,如，代表节点业和市点有

一条边权为u的边

2≤n≤1052\le n\le 10^5

0≤m≤1050\le m\le 10^5

1≤u,v≤n1\le u,v\le n

1≤w≤1091\le w\le 10^9

输出描述

如果该无向图初始的连通块的数量不小于3，则输出-1

否则输出一个整数，代表塔子哥可以获得的最大价值

样例1

输入

3 3
1 2 4
2 3 3
1 3 2

输出

7

说明

删除前两条边即可，这样有两个连通块:节点1和节在3的连通块，节点2自己为一个连通块。

样例2

输入

4 2
1 2 4
3 4 3

输出

0

说明

初始即为两个连通块，无法删除任何边

知识点:*****

查看知识点以及同类型题目

Statistics