#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<cstring>
using namespace std;
const int N=202;
int g[N][N];
unordered_set<int> s;
int q[305];
int n,m,k;
int main()
{
    memset(g,0x3f,sizeof g);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,w;cin>>a>>b>>w;
        g[a][b]=g[b][a]=w;

    }
    cin>>k;
    int res,dist=0x3f3f3f3f/2;
    for(int i=1;i<=k;i++)
    {
        int j;cin>>j;
        int sum=0;
        s.clear();
        bool vaild=false;
        for(int l=0;l<j;l++)
       {

        cin>>q[l];
        s.insert(q[l]);
        if(l) 
        {
         if(g[q[l]][q[l-1]]==0x3f3f3f3f) 
         {
              vaild=true;
         }
            sum+=g[q[l]][q[l-1]];
        }
        }

         if(vaild) printf("Path %d: NA (Not a TS cycle)",i);
         else if(q[0]!=q[j-1]||s.size()<n)  printf("Path %d: %d (Not a TS cycle)",i,sum);
         else
         {
         if(j>n+1) printf("Path %d: %d (TS cycle)",i,sum);
         else printf("Path %d: %d (TS simple cycle)",i,sum);
         if(sum<dist)
    {
        dist=sum;
        res=i;
    }


         }




        cout<<endl;
    }


    printf("Shortest Dist(%d) = %d",res,dist);

    return 0;
}