#include <bits/stdc++.h>

#define pii pair<int,int>

using namespace std;

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

    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;
            }
        }
    }

    ///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<long long int> dis=bellman_ford(node, edge, adj);


    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<<dis[dst]<<endl;
        }
    }

    return 0;
}