#include<iostream>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

const int N = 1e3 + 10;

int n,m;

vector<int>v[N][30];
int mp[N][N];

int dist[N][N];

struct node{
    int x,y,sum;
    bool operator < (const node &p)const{
        return sum > p.sum;
    }
};

int flag[N][N],ans = 0x3f3f3f3f;
void dij(){
    memset(dist,0x3f,sizeof dist);
    priority_queue<node>q;
    q.push({1,n,0});
    dist[1][n] = 0;
    while(q.size()){
        node p = q.top();
        q.pop();
        if(flag[p.x][p.y]) continue;
        flag[p.x][p.y] = 1;
        if(p.x == p.y){
            ans = min(ans,dist[p.x][p.y]);
        }
        if(mp[p.x][p.y]) ans = min(ans,dist[p.x][p.y] + 1);
        for(int i = 0; i <= 25; i++){
            for(auto j : v[p.x][i]){
                for(auto k : v[p.y][i]){
                    if(dist[j][k] > dist[p.x][p.y] + 2){
                        dist[j][k] = dist[p.x][p.y] + 2;
                        q.push({j,k,dist[j][k]});
                    }
                }
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a,b;char c;
        scanf("%d %d %c",&a,&b,&c);
        v[a][c - 'a'].push_back(b);
        v[b][c - 'a'].push_back(a);
        mp[a][b] = 1;
        mp[b][a] = 1;
    }

    dij();

    if(ans == 0x3f3f3f3f) cout << -1 <<endl;
    else cout << ans <<endl;




    return 0;
}
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;

#define rep(i, n) for(int i = 0, i##_len=(n); i < i##_len; ++i)
#define per(i, n) for(int i = (n)-1; i >= 0 ; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(x) ((int)(x).size())

void _cin() {} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail) { cin >> head; _cin(forward<Tail>(tail)...); }
#define cin(Type, ...) Type __VA_ARGS__; _cin(__VA_ARGS__)
#define cinv(Type, xs, n) vector<Type> xs(n); rep(i, n) cin >> xs[i]
#define cinv2(Type, xs, ys, n) vector<Type> xs(n), ys(n); rep(i, n) cin >> xs[i] >> ys[i]
#define cinv3(Type, xs, ys, zs, n) vector<Type> xs(n), ys(n), zs(n); rep(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define cinvv(Type, xs, h, w) vector<vector<Type>> xs(h, vector<Type>(w)); rep(i, h) rep(j, w) cin >> xs[i][j]

void print() { cout << endl; }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(tail) != 0) cout << " "; print(forward<Tail>(tail)...); }
template <class Type> void print(vector<Type> &vec) { for (auto& a : vec) { cout << a; if (&a != &vec.back()) cout << " "; } cout << endl; }
template <class Type> void print(vector<vector<Type>> &df) { for (auto& vec : df) { print(vec); } }

void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void yesno(bool b) { cout << (b ? "yes" : "no") << endl; }
template<class Integer>bool chmax(Integer &a, const Integer &b) { if (a < b) { a = b; return 1; } return 0; }
template<class Integer>bool chmin(Integer &a, const Integer &b) { if (b < a) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
//using mint = modint1000000007;

void Main() {
	cin(int, n);
	vector<ll> op = { 0ll, -1ll*(1ll<<50), 1ll << 50 };
	int lo = 2;
	rep(i, n) {
		cin(ll, a, t);
		if (t == 1ll) {
			op[0] += a;
			op[1] += a;
			op[2] += a;
		}
		else if (t == 2ll) {
			chmax(op[1], a);
			chmax(op[2], a);
			lo = 2;
		}
		else if (t == 3ll) {
			chmin(op[1], a);
			chmin(op[2], a);
			lo = 3;
		}
	}
	cin(int, q);
	while (q--) {
		cin(ll, x);
		if(lo==2)	print(max(op[1], min(op[2],x + op[0])));
		else print(min(op[2], max(op[1],x + op[0])));
	}
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//cout << fixed << setprecision(16);
	//int t; cin >> t; while (t--)
	Main();
}