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