#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define LL long long int
vector<pair<LL,LL> > adj[100001];
vector <LL> djikstra(LL src,LL N)
{
    vector <LL> dis(N,INT_MAX);
    priority_queue< pair<LL,LL> ,vector< pair <LL,LL> >, greater< pair<LL,LL> > > pq;
    for(auto it:adj[src])
    {
    	pq.push(it);
    	dis[it.second]=it.first;
    }
    while(!pq.empty())
    {
        pair <LL,LL> temp=pq.top();
        pq.pop();
        LL s=temp.second;
        for(auto it:adj[s])
        {
            if( dis[it.second]  > dis[s] + it.first )
            {
                dis[it.second]= dis[s] + it.first;
                pq.push({dis[s] + it.first,it.second});
            }
        }
    }
    return dis;
}
int main()
{
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	LL  N,M;
	cin >> N >> M;
	map< pair<LL,LL> ,LL > hash;
	map<LL,LL> Self;
	for(LL i=0;i<N;i++)
	{
		Self[i]=INT_MAX;
	}
	for(LL i=0;i<M;i++)
	{
		LL x,y,z;
		cin>>x>>y>>z;
		x--;
		y--;
		if(x==y)
		{
			Self[x]=min(Self[x],z);
		}
		if( hash.find( {x,y} )==hash.end())
		{
			hash[{x,y}]=z;		
		}
		else
		{
			hash[{x,y}]=min(hash[{x,y}],z);
		}
	}
	for(auto it:hash)
	{
		adj[it.first.first].push_back({it.second,it.first.second});
	}
	for(LL i=0;i<N;i++)
	{
		vector<LL> arr= djikstra(i,N);
		if(arr[i]==INT_MAX)
        {
          	if(Self[i]==INT_MAX)
			cout<<-1<<endl;
          else
            cout<<Self[i]<<endl;
        }
		else
			cout<<arr[i]<<endl;
	}

}

#include <bits/stdc++.h>
using namespace std;
int N, Q;
const int maxn = 2e5 + 5;
typedef long long ll;
inline ll read()
{
    ll x = 0;
    int s = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            s = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
    {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x * s;
}
int main()
{
    int N, Q;
    N = read();
    ll a, t;
    ll l = -1e9, r = 1e9, b = 0;
    for (int i = 0; i < N; i++)
    {
        a = read();
        t = read();
        if (t == 1)
        {
            l += a;
            r += a;
            b += a;
        }
        else if (t == 2)
        {
            l = max(l, a);
            r = max(r, a);
        }
        else
        {
            l = min(l, a);
            r = min(r, a);
        }
    }
    Q = read();
    while (Q--)
    {
        ll x = read() + b;
        if (x < l)
            cout << l;
        else if (x > r)
            cout << r;
        else
            cout << x;
        cout << ' ';
    }
}