まず、一切の制約がない時に島 \(i\) から島 \(j\) まで移動するのにかかる時間を \(t(i,j)\) とします。（なお、特に \(i=j\)（始点と終点の島が同じ）の場合は \(t(i,j)=0\) とします。）
これはワーシャルフロイド法などですべての島の組み合わせについて全体で \(O(N^3)\) の計算量で求めることができます。

\(i\) 番目 (\(1\leq i\leq Q\)) の問題を解くことを考えます。
その問題においてわたる必要のある橋が結んでいる島はそれぞれ \((U_{B_{i,1}}, V_{B_{i,1}})\) , \((U_{B_{i,2}}, V_{B_{i,2}})\) , \(\ldots\), \((U_{B_{i,K_i}}, V_{B_{i,K_i}})\) です。
指定された橋をわたる順番（ \(K_i!\) 通り）およびそれぞれのわたる向き（ \(2^{K_i}\) 通り）を \(1\) つ定め、具体的には \(x_1\to y_1\), \(x_2\to y_2\), \(\ldots\), \(x_{K_i}\to y_{K_i}\) の順でその向きにわたることにしたとします。このとき、条件をみたすように島 \(1\) から島 \(N\) へ移動するのにかかる最小の時間は、

\[ \left[ t(1,x_1)+t(y_1,x_2)+t(y_2,x_3)+\cdots+t(y_{K_i-1},x_{K_i})+t(y_{K_i},N)\right] +\left[T_{B_{i,1}}+T_{B_{i,2}}+\cdots+T_{B_{i,K_i}} \right] \]

となります。最終的な答えはすべてのあり得る順番および向きにおけるこの値の最小値です。

この値は事前に \(t(i,j)\) を求めておけば各場合について \((2K_i+1)\) 個の数字の合計として計算できるため、\(1\) つの問題あたりの計算回数は \((2K_i+1)\cdot (K_i!)\cdot 2^{K_i}\) 回程度となり、今回の制約 \((K_i\leq 5)\) のもとで最大 \(11\cdot(5!)\cdot 2^5\sim 4\times 10^4\) 程度となります。問題は高々 \(3000\) 個であるため、全体で \(10^8\) 回程度の足し算および比較となり十分高速です。
よってこの問題を解くことができました。

なお、橋をわたる順番を \(1\) つ決めた後、向きについては動的計画法を使うことによって、\(1\) つの問題を解くために必要な計算回数が \(\sim 5K_i\cdot (K_i!)\) 回程度となり、より高速に問題を解くことができます。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define ll long long

#define N 400
#define M (int)2e+5
#define INF (ll)1e+15

int n;
int u[M],v[M];
ll t[M];
ll d[N][N];
int k;
vector<int>a;

ll solve(void){
	ll ans=INF;
	ll dp[5][2];
	vector<int>b;
	rep(i,k)b.push_back(i);
	while(true){
		dp[0][0]=d[0][v[a[b[0]]]]+t[a[b[0]]];
		dp[0][1]=d[0][u[a[b[0]]]]+t[a[b[0]]];
		rep(i,k-1){
			dp[i+1][0]=min(dp[i][0]+d[u[a[b[i]]]][v[a[b[i+1]]]],dp[i][1]+d[v[a[b[i]]]][v[a[b[i+1]]]])+t[a[b[i+1]]];
			dp[i+1][1]=min(dp[i][0]+d[u[a[b[i]]]][u[a[b[i+1]]]],dp[i][1]+d[v[a[b[i]]]][u[a[b[i+1]]]])+t[a[b[i+1]]];
		}
		ans=min(ans,dp[k-1][0]+d[u[a[b[k-1]]]][n-1]);
		ans=min(ans,dp[k-1][1]+d[v[a[b[k-1]]]][n-1]);
		if(!(next_permutation(b.begin(),b.end())))break;
	}
	return ans;
}


int main() {
	int m,q,x;
	
	cin>>n>>m;
	rep(i,n)rep(j,n){
		if(i==j)d[i][j]=0;
		else d[i][j]=INF;
	}
	rep(i,m){
		cin>>u[i]>>v[i]>>t[i];
		u[i]--,v[i]--;
		d[u[i]][v[i]]=min(d[u[i]][v[i]],t[i]);
		d[v[i]][u[i]]=min(d[v[i]][u[i]],t[i]);
	}
	rep(i1,n)rep(i0,n)rep(i2,n)d[i0][i2]=min(d[i0][i2],d[i0][i1]+d[i1][i2]);
	cin>>q;
	rep(qq,q){
		cin>>k;
		a.clear();
		rep(kk,k){
			cin>>x;
			a.push_back(x-1);
		}
		cout<<(solve())<<endl;
	}
	return 0;
}