Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem F: 最小生成树

Problem F: 最小生成树

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 71  Solved: 16
[Submit][Status][Web Board]

Description

ap最近学习了最小生成树树之后,向你提了这么一个问题:给一个n个节点的完全图,节点编号从1-n, 如果限制这个完全图的生成树中k个点的度数为1,那么还能否构造出最小生成树呢?

Input

第一行一个正整数T,代表有T组数据
每组数据,第一个两个正整数n, k (2 <= n <= 300, 0 <= k <= n)
接下来n*(n-1)/2行,每行三个正整数ui, vi, wi, 代表节点ui和节点vi之间有一条权值为wi的边 (0 <= wi <= 10000)
最后一行, k个互不相同的数fi, 代表限制度数为1的节点的编号
输入保证给出的是完全图

Output

每组数据,若符合条件的最小生成树存在,输出该最小生成树所有边权之和; 若不存在, 输出-1

Sample Input

3
3 0
1 2 1
2 3 2
3 1 3

3 1
1 2 1
2 3 2
3 1 3
2
3 3
1 2 1
2 3 2
3 1 3
1 2 3

Sample Output

3
4
-1

HINT

[Submit][Status][Web Board]