拆地毯

直观理解

会场里有 \(n\) 个"关键区域"，用 \(m\) 条无向地毯（边）把它们连接起来。 每条地毯用三个数表示：\((u, v, w)\)，意思是"在 \(u\) 区域和 \(v\) 区域之间铺了一条美丽度为 \(w\) 的地毯"。

现在典礼结束，要把地毯拆掉。但为了节省，允许最多保留 \(K\) 条地毯。 唯一的硬性要求：保留下来的地毯不能形成环——也就是保留后的图的每个连通块都要是树（或空）。 问：在满足"不成环"和"最多 \(K\) 条"这两个条件下，能让美丽度总和最大的值是多少？

关键词翻译：

• "不成环" = 任意连通块中，任意两点之间的简单路径唯一（等价于无环）。
• "最多 \(K\) 条" = 可以选少于 \(K\) 条，也可以正好 \(K\) 条。

输入格式

• 第一行：三个正整数 \(n, m, K\)
• 接下来 \(m\) 行：每行三个正整数 \(u, v, w\)，表示一条无向地毯连接 \(u\) 与 \(v\)，美丽度为 \(w\)

输出格式

• 输出一个整数：在满足"无环"且"保留条数 ≤ \(K\)"前提下，选出的地毯美丽度总和的最大值。

样例

输入

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

输出

22

说明 可以保留第 \(1\), \(2\), \(4\) 条地毯，总和为 \(10 + 9 + 3 = 22\)，且不成环。 如果保留第 \(1\), \(2\), \(3\) 条地毯，总和 \(10 + 9 + 7 = 26\)，但 \(1\text{-}2\text{-}3\) 形成了环，不符合要求。

约束

• \(1 \le n, m, K \le 10^5\)
• \(1 \le u, v \le n\)，\(u \ne v\)
• 边为无向图