题目背景

一座古老的吊桥年久失修,桥面由若干根绳索连接各个支柱。现需要对吊桥进行翻新,但经费有限,只能保留至多 $K$ 根绳索。请你帮忙选出这些绳索,使得保留的绳索总承重最大,同时保留后的结构不能出现环路。

题目描述

吊桥共有 $n$ 个支柱,支柱之间由 $m$ 根绳索连接。每根绳索由三个整数 $u$、$v$、$w$ 表示,其中 $u$ 和 $v$ 为绳索连接的两个支柱编号,$w$ 为这根绳索的承重能力。

由于预算有限,只能保留至多 $K$ 根绳索,且保留的绳索构成的图中,任意可互相到达的两个支柱间只能有一种方式互相到达。换言之,保留的结构不能有环。现在需要你帮忙算出这至多 $K$ 根绳索的承重之和最大为多少。

输入格式

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

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

输出格式

只包含一个正整数,表示这 $K$ 根绳索的承重之和的最大值。

样例

5 4 3
1 2 10
1 3 9
2 3 7
4 5 3

22

提示

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