题目描述

大土豆有一个$n$个点$m$条边的简单无向图，图中的边有边权。一个连通块是一朵花当且仅当对于某个给定的整数$k$，连通块中的点数比边数多至少$k$。

现在大土豆希望你找出原图中边集$E$的一个子集$E'$，使得原图中的所有节点构成的点集，和$E'$组成的新图中，每个连通块都是一朵花。你需要最大化这个边集的权值和。

输入格式

第一行输入三个整数$n,m,k$，代表图的点数，边数，和花的限制。

接下来$m$行，每行输入三个整数$u,v,w$，代表图中连接$u,v$的边权值为$w$。

输出格式

输出一行一个整数代表答案。

输入样例1

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

输出样例1

7

输入样例2

6 7 0
1 2 7
2 3 6
3 1 5
3 4 1
4 5 4
5 6 3
6 4 2

输出样例2

27

样例3见下载文件。

数据范围

对于$20\%$的数据，保证$1\leq n,m\leq 20$。

对于另外$20\%$的数据，保证$k=1$。

对于另外$20\%$的数据，保证$w=1$。

对于所有数据，保证$1\leq n\leq 5\times 10^5,1\leq m\leq \min(\frac{n(n-1)}{2},5\times 10^5),k\in\{0,1\}$,$1\leq u,v\leq n,1\leq w\leq 10^6$，保证没有重边和自环。

点此下载