*E diff 1301

floyd 搜索
注意到必经边 $k$ 非常小，于是直接枚举经过顺序。求距离使用floyd。注意每条边可以正着或反着走。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,kk,ans;
const int N=401;
int dp[N][N];
int usd[N];
int ord[N];
int mhash1[N];
int mhash2[N];
struct node
{
	int x;
	int y;
	int z;
}edge[1000005];
void dfs2(int k)
{
	if(k==kk+1)
	{
		int sum=0;
		int st=1;
		int ed=0;
		for(int i=1;i<=kk;i++)
		{
			int x=edge[ord[i]].x;
			int y=edge[ord[i]].y;
			if(mhash2[i]==-1)
			swap(x,y);
			ed=x;
			sum+=dp[st][ed];
			st=y;
		}
		sum+=(dp[st][n]);
		ans=min(ans,sum);
		return ;
	}
	mhash2[k]=1;
	dfs2(k+1);
	mhash2[k]=-1;
	dfs2(k+1);
}
void dfs1(int k)
{
	if(k==kk+1)
	{
		dfs2(1);
		return ;
	}
	for( int i=1;i<=kk;i++ )
	if(!mhash1[i])
	{
		mhash1[i]=1;
		ord[k]=usd[i];
		dfs1(k+1);
		mhash1[i]=0;
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dp[i][j]=1e15;
	for(int i=1;i<=n;i++)
		dp[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		edge[i].x=x;
		edge[i].y=y;
		edge[i].z=z;
		dp[x][y]=min(dp[x][y],z);
		dp[y][x]=min(dp[y][x],z);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>kk;
		ans=1e13;
		int jishu=0;
		for(int i=1;i<=kk;i++)
		{
			cin>>usd[i];
			jishu+=edge[usd[i]].z;
		}
		dfs1(1);
		cout<<jishu+ans<<endl;
	}
	return 0;
}