#Psmt15. 1.连接云朵

1.连接云朵

1.连接云朵

题目描述

现在给你云朵的个数N,再给你M个关系,表示哪些云朵可以连在一起。小明要把所有云朵连成K个棉花糖,一个棉花糖最少要用掉一朵云,小明想知道他怎么连,花费的代价最小。

输入格式

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

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

输出格式

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

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

数据范围

(原站未提供,导入后需人工补齐)

样例

3 1 2
1 2 1
1
3 1 1
1 2 1
No Answer 

提示

对于30%的数据:N<=100,M<=1000。

对于100%的数据:1<=N<=1000,1<=M<=10000,1<=K<=10,1<=X,Y<=N,0<=L<=10000。