最近vvvb沉迷某游戏，而游戏中繁杂的支线任务需要vvvb操控主角频繁在不同地点间奔波，还不允许快速传送，这让他非常恼火。
现在，已知该游戏大地图上共包含n个地点，这n个地点互相之间通过m条道路连接，每条道路都有长度，整个大地图保证是连通的。现在vvvb位于他的家中（1号地点），他手上共接取了q个支线任务，他打算先完成全部支线任务后再去冲主线。每个支线都需要你依序前往若干个地点，这些地点可能包含重复地点，现在vvvb想请你给他一种最好的方案，使得他完成全部支线任务需要跑的路最少。
本题为多组样例，第一行一个正整数T 1≤T≤10表示数据组数。
对于每组数据，第一行三个正整数n,m,q(3≤n≤100,n−1≤m≤2n(n−1),1≤q≤5)，分别表示地图上地点数目，道路数目和vvvb接取的支线数目。
接下来m行每行包含三个正整数u,v,w(1≤u,v≤n,1≤w≤100)，表示地点u和地点v之间存在一条长度为w的道路。
接下来q行，每行表示一个支线，首先一个正整数k(1≤k≤9)，表示完成该支线一共需要前往的地点数目，然后跟随k个正整数依次表示这k个地点。
对于每组数据输出一行一个正整数表示vvvb完成全部支线最少需要跑多少长度的路。
2
4 4 2
1 2 2
1 3 1
2 3 5
3 4 2
3 2 4 1
4 2 3 4 2
3 2 1
1 2 2
2 3 1
3 2 3 1
12
6
按照如下顺序跑支线最佳（数字代表地点，括号里为对应的支线序号）：
样例1：2(1)-2(2)-3(2)-4(2)-4(1)-1(1)-2(2)
样例2：2(1)-3(1)-1(1)