//combinatorial optimization组合优化   optimization n.优化  operations research运筹学

//It is an NP-hard problem in combinatorial optimization, 
//important in operations research and theoretical computer science.
//它是组合优化中的一个NP难题，在运筹学和理论计算机科学中具有重要意义。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 210;

/*
简单回路：
    1.有无长度
    2.每个点是否能到
    3.是否是回路:起点和终点是否一致
    4.点数是否是n+1(保证每一个点只走一次)
不是简单回路：
    1.有无长度
    2.每个点是否能到
    3.是否是回路:起点和终点是否一致
不是回路：
    1.没有长度
*/

int n,m;
int d[N][N],vers[310];
bool st[N];

int main()
{
    cin>>n>>m;
    memset(d,0x3f,sizeof d);
    for(int i = 0; i<m; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b] = d[b][a] = c;
    }

    int k; cin>>k;
    int min_dist = 0x3f3f3f3f,min_id;

    for(int g = 1; g<=k; g++)
    {
        int cnt;
        cin>>cnt;
        for(int i = 0; i<cnt; i++) cin>>vers[i];

        int sum = 0;
        bool success = true;//判断两个点是否有长度,即是否可以组成回路
        memset(st,0,sizeof st);

        for(int i = 0; i+1<cnt; i++)
        {
            int a = vers[i],b = vers[i+1];
            if(d[a][b] == 0x3f3f3f3f)
            {
                sum = -1;
                success = false;
                break;
            }
            sum += d[a][b];
            st[a] = true;//标记所有走过的点
        }
        for(int i = 1; i<=n; i++)
            if(!st[i])//如果有一个点没有走过,即不是回路
            {
                success = false;
                break;
            }
        //起点和终点不一致
        if(vers[0] !=vers[cnt-1]) success = false;
        if(sum == -1) cout<<"Path "<<g<<": NA (Not a TS cycle)"<<endl;
        else
        {
            if(!success) cout<<"Path "<<g<<": "<<sum<<" (Not a TS cycle)"<<endl;
            else//是回路
            {
                //点数是n+1,每个点只走一次，是简单回路
                if(cnt == n+1) cout<<"Path "<<g<<": "<<sum<<" (TS simple cycle)"<<endl;
                else cout<<"Path "<<g<<": "<<sum<<" (TS cycle)"<<endl;
                //找出最接近旅行商问题解决方案的回路编号，即其中的最短路径
                if(sum <min_dist) min_dist = sum,min_id = g;
            }
        }
    }
    cout<<"Shortest Dist("<<min_id<<") = "<<min_dist<<endl;
    return 0;
}