A21507.口袋的天空

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖。
给你云朵的个数 NN,再给你 MM 个关系,表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 KK 个棉花糖,一个棉花糖最少要用掉一朵云,小杉想知道他怎么连,花费的代价最小。

输入格式

第一行有三个数 N,M,KN,M,K

接下来 MM 行每行三个数 X,Y,LX,Y,L,表示 XX 云和 YY 云可以通过 LL 的代价连在一起。

输出格式

对每组数据输出一行,仅有一个整数,表示最小的代价。

如果怎么连都连不出 KK 个棉花糖,请输出 No Answer

输入输出样例

  • 输入#1

    3 1 2
    1 2 1
    

    输出#1

    1

说明/提示

对于 30%30\% 的数据,1N1001 \le N \le 1001M1031\le M \le 10^3

对于 100%100\% 的数据,1N1031 \le N \le 10^31M1041 \le M \le 10^41K101 \le K \le 101X,YN1 \le X,Y \le N0L<1040 \le L<10^4

首页