1 //我看过Discuss说不能用克鲁斯卡尔因为有很多边
2 //但是只能用G++过，C++的确超时
3 #include <stdio.h>
4 #include <string.h>
5 #include <algorithm>
6 using namespace std;
7
8 struct node
9 {
10 int a, b, cost;
11 }c[30000];
12 int fa[505];
13
14 void init(int n)
15 {
16 for (int i = 1; i <= n; i++)
17 fa[i] = i;
18 }
19
20 bool cmp(node x, node y)
21 {
22 return x.cost<y.cost;
23 }
24
25 int find(int x)
26 {
27 if (fa[x] != x) fa[x] = find(fa[x]);
28 return fa[x];
29 }
30
31 int main()
32 {
33 int n, k, m, ncase;
34 scanf("%d", &ncase);
35 while (ncase--)
36 {
37 scanf("%d %d %d", &n, &k, &m);
38 init(n); //初始化
39 for (int i = 0; i<k; i++)
40 scanf("%d %d %d", &c[i].a, &c[i].b, &c[i].cost);
41 for (int i = 1; i <= m; i++)
42 {
43 int x, pos, pos1;
44 scanf("%d %d", &x, &pos);
45 for (int j = 1; j<x; j++)
46 {
47 scanf("%d", &pos1);
48 c[k].a = pos, c[k].b = pos1, c[k].cost = 0;
49 pos = pos1;
50 k++;
51 }
52 }
53
54 sort(c, c + k, cmp);
55 int sum = 0;
56 for (int i = 0; i<k; i++)
57 {
58 int x = find(c[i].a);
59 int y = find(c[i].b);
60 if (x != y)
61 sum += c[i].cost, fa[x] = y;
62 }
63
64 int count = 0;
65 for (int i = 1; i <= n; i++)
66 if (fa[i] == i)
67 count++;
68
69 if (count != 1)
70 printf("-1
");
71 else
72 printf("%d
", sum);
73 }
74 return 0;
75 }
