#include<bits/stdc++.h>
using namespace std;
#define up(i,l,r) for(int i=l;i<=r;++i)
#define dn(i,l,r) for(int i=l;i>=r;--i)
#define int long long
const int N=405;
int ds[N][N],n,m,q,k,c[10];
int u[200005],v[200005],t[200005],re;
int mn=1e14,a[N],lst,sum;
bool vs[N];
void dfs(int x){
	if(x==k+1){
		up(S,0,(1<<k)-1){
			lst=1;
			sum=0;
			up(j,0,k-1){
				re=j+1;
				if(S>>j&1){
					sum+=ds[lst][u[c[a[re]]]]+t[c[a[re]]];
					lst=v[c[a[re]]];
				}else{
					sum+=ds[lst][v[c[a[re]]]]+t[c[a[re]]];
					lst=u[c[a[re]]];
				}
			} 
			sum+=ds[lst][n];
			mn=min(mn,sum);
		}
		return;
	}
	up(i,1,k){
		if(!vs[i]){
			vs[i]=1;
			a[x]=i;
			dfs(x+1);
			vs[i]=0;
		}
	}
} 
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m;
	up(i,1,n){
		up(j,1,n){
			ds[i][j]=1e14;
		} 
		ds[i][i]=0;
	}
	up(i,1,m){
		cin>>u[i]>>v[i]>>t[i];
		ds[u[i]][v[i]]=min(ds[u[i]][v[i]],t[i]);
	}
	up(k,1,n){
		up(i,1,n){
			up(j,1,n){
				ds[i][j]=min(ds[i][j],ds[i][k]+ds[k][j]);
			}
		} 
	}
	cin>>q;
	up(i,1,q){
		cin>>k;
		up(j,1,k) cin>>c[j];
		up(j,1,10) vs[j]=0;
		mn=1e14;
		dfs(1);
		cout<<mn<<'\n';
	}
	return 0;
}
//tomxi