口袋的天空

题目背景

小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空。 有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖。

题目描述

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

输入输出格式

输入格式


每组测试数据的 第一行有三个数$N,M,K(1 \le N \le 1000,1 \le M \le 10000,1 \le K \le 10)$ 接下来$M$个数每行三个数$X,Y,L$,表示$X$云和$Y$云可以通过$L$的代价连在一起。$(1 \le X,Y \le N,0 \le L<10000)$ $30\%$的数据$N \le 100,M \le 1000$

输出格式


对每组数据输出一行,仅有一个整数,表示最小的代价。 如果怎么连都连不出$K$个棉花糖,请输出'No Answer'。

输入输出样例

输入样例 #1

3 1 2
1 2 1

输出样例 #1

1

说明

厦门一中YMS原创