题目描述

华莱市一共有 $N$ 个居民点，居民点之间有 $M$ 条双向道路相连。这些居民点两两之间都可以通过一些双向道路到达。这种情况一直持续到最近，一次严重的地震毁坏了 $Q$ 条道路。

震后，小K打算修复其中一些道路，修理第 $i$ 条道路需要花费 $P_i$ 。现在想要所有的城市恢复联通，需要的最小花费是多少？

你能帮助小 $K$ 计算出需要的最少花费么？

输入格式

第一行三个正整数 $N$ 、 $M$、 $Q$ ，含义如题面所述。

接下来M行，每行三个正整数$X_i、Y_i、P_i$，表示一条连接 $X_i$ 和 $Y_i$ 的双向道路，修复需要 $P_i$ 的花费。可能有自环，可能有重边。

这M条路其中前 $M-K$ 条是完好的，后 $K$ 条是被震坏的。

数据范围与提示

对于40%的数据，$N \leq 2000,M,Q \leq 5000$

对于100%的数据，$N \leq 50000,Q < M \leq 2*10^5. P_i<=10^6$ .$X_i$ 、$Y_i$ 均在$[1,N]$范围内。