//题目回忆：n个点，m个桥梁，给定k个桥梁，求从1到n，且经过给定桥梁的最小值
//看数据范围，k，N都很小，直接爆搜即可
//当从一个桥梁走到另一个桥梁时，一定走最小值，因此保存最小值floyd
//走到给定桥梁后，加上给定的桥梁值即可（注意不是最小值，脑子糊涂了）
#include <iostream>
#include <vector>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef long long LL;

const int N = 410,M = 2e5+10;

typedef pair<int,int>PII;

LL dist[N][N];
int b[M];

int k;
int n,m;
LL ans;
bool used[N];
PII g[M];
LL w[M];

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=n;j++)
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}

void dfs(int u,int now,LL sum)
{
    //cout<<u<<" "<<now<<" "<<sum<<endl;
    if(u>k)
    {
        ans=min(ans,sum+dist[now][n]);
        return;
    }
    for(int i=1;i<=k;i++)
        if(!used[i])
        {
            used[i]=true;
            //cout<<u<<" "<<i<<" "<<b[i]<<" "<<g[b[i]].y<<" "<<sum<<" "<<dist[now][g[b[i]].x]<<" "<<dist[g[b[i]].x][g[b[i]].y]<<endl;
            dfs(u+1,g[b[i]].y,sum+dist[now][g[b[i]].x]+w[b[i]]);
            dfs(u+1,g[b[i]].x,sum+dist[now][g[b[i]].y]+w[b[i]]);
            used[i]=false;
        }
}

int main()
{
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m;
    for(int i=1;i<=n;i++) dist[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        LL a,b,c;
        cin>>a>>b>>c;
        g[i]={a,b};
        dist[a][b]=min(c,dist[a][b]);
        dist[b][a]=min(c,dist[b][a]);
        w[i]=c;
    }
    int q;
    cin>>q;
    floyd();
    while(q--)
    {
        memset(used,0,sizeof used);
        ans=1e18;
        cin>>k;
        for(int i=1;i<=k;i++) cin>>b[i];
        dfs(1,1,0);
        cout<<ans<<endl;
    }
}