#include <bits/stdc++.h>

#define pii pair<int,int>

using namespace std;

void path_print(int dst, vector<int> &parent)
{
    if(dst==-1) return;
    path_print(parent[dst], parent);
    cout<<dst<<" ";
}

vector<long long int> bellman_ford(int node, int edge, vector<pair<pii, int> > &adj,  vector<int> &parent)
{
    vector<long long int> dis(node, INT_MAX);
    dis[0]=0;
    parent[0]=-1;

    for(int i=0; i<node; i++)
    {
        for(int j=0; j<edge; j++)
        {
            int u=adj[j].first.first;
            int v=adj[j].first.second;
            int cost=adj[j].second;
            if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
                parent[v]=u;
            }
        }
    }

    ///Running the loop one more time to find out whether the graph contains any negative cycle loop or not

    //bool neg_cycle=0; //To detect whether any negative cycle present in the graph or not
    for(int j=0; j<edge; j++)
    {
        int u=adj[j].first.first;
        int v=adj[j].first.second;
        int cost=adj[j].second;
        if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
        {
            /*
            neg_cycle=1;
            break;
            */
            dis[v]=INT_MAX; //Marking the nodes which will keep decreasing infinitly due to negative weight cycle
        }
    }
    return dis;
}


int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int node,edge;
    cout<<"Enter the number of nodes: ";
    cin>>node; //assuming 0<=node
    cout<<"Enter the number of edges: ";
    cin>>edge;

    vector<pair<pii, int> > adj;


    for(int i=0; i<edge; i++)
    {
        int from, to, cost;
        cin>>from>>to>>cost;
        adj.push_back({{from, to}, cost});
    }

    //Taking "long long int" instead of "int" because adding up costs can cause overflow of integer
    vector<int> parent(node);
    vector<long long int> dis=bellman_ford(node, edge, adj, parent);


    int q;
    cout<<"Enter how many queries you want to make: ";
    cin>>q;
    for(int i=0; i<q; i++)
    {
        int dst;
        cout<<"Enter the destination: ";
        cin>>dst;
        if(dis[dst]==INT_MAX)
        {
            cout<<"Due to some negative cycle, this destination can't be reached."<<endl;
        }
        else
        {
            cout<<"The lowest cost is: "<<dis[dst]<<endl;
            cout<<"And the path is: ";
            path_print(dst, parent);
        }
    }

    return 0;
}