2090: 【入门】片区划分
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：9
解决：1
题目描述
A市有n个村庄（村庄编号为1~n），现准备将n个村庄划分为k个区（一个区中要有至少1个村庄），同一个区中的村庄要求有道路可以互相到达（不一定要直达，比如：A村要去C村，可以先先去B村，再去C村）。
为了节约成本，在划分之前，相关规划部门调研了村庄之间修路的成本，本次调研，共调研到了m条道路的建设成本。
假设所有村庄之间目前没有任何道路，如果要将n个村庄划分为k个区，请求出最少的修路成本？
输入
第一行有三个数n,m,k(1≤n≤1000,1≤m≤10000,1≤k≤10)
接下来m行每行三个数x,y,l，表示编号为x村到编号为y村修路的费用。(1≤x,y≤n,0≤l<10000)
测试数据保证x村到y村的道路只有1条。
输出
输出一个整数，代表最少的修路成本。
如果按照当前的调研数据，无法将n个村庄划分为k个区，请输出"No Answer"（比如，假设有5个村庄，只有2条道路的建设数据，是无法将5个村庄划分为2个区或者1个区的）。
如果按照当前的调研数据，无法将n个村庄划分为k个区，请输出"No Answer"（比如，假设有5个村庄，只有2条道路的建设数据，是无法将5个村庄划分为2个区或者1个区的）。
样例输入 复制
3 1 2
1 2 1样例输出 复制
1提示
【样例解释】
1号村到2号村修路成本为1。
样例要求将3个村划分为2个区，只需要修1条路就可以将2个村合并为1个区，加上剩余的1个村，形成了2个区。
因此，样例中只需要在1号村和2号村之间修路，就可以实现划分2个区的目标。