J. 拆地毯

Type: RemoteJudge

1000ms

125MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

还记得 NOIP 2011 提高组 Day1 中的铺地毯吗？时光飞逝，光阴荏苒，三年过去了。组织者精心准备的颁奖典礼早已结束，留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。

会场上有 $n$ 个关键区域，不同的关键区域由 $m$ 条无向地毯彼此连接。每条地毯可由三个整数 $u$ 、 $v$ 、 $w$ 表示，其中 $u$ 和 $v$ 为地毯连接的两个关键区域编号， $w$ 为这条地毯的美丽度。

由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留至多 $K$ 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。现在组织者求助你，想请你帮忙算出这至多 $K$ 条地毯的美丽度之和最大为多少。

第一行包含三个正整数 $n$ 、 $m$ 、 $K$ 。

接下来 $m$ 行中每行包含三个正整数 $u$ 、 $v$ 、 $w$ 。

只包含一个正整数，表示这 $K$ 条地毯的美丽度之和的最大值。

选择第 $1$ 、 $2$ 、 $4$ 条地毯，美丽度之和为 $10 + 9 + 3 = 22$ 。

若选择第 $1$ 、 $2$ 、 $3$ 条地毯，虽然美丽度之和可以达到 $10 + 9 + 7 = 26$ ，但这将导致关键区域 $1$ 、 $2$ 、 $3$ 构成一个环，这是题目中不允许的。

$1\le n,m,k \le 10^5$ 。