#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 22, MOD = (int)1e9 + 7;
const ll inf = 1e18;

int n, m;
ll d[N][N], c[N], dp[(1 << 19) + 1][20], s[(1 << 19) + 1];
void prec() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
            }
        }
    }
    for(int i = 0; i < (1 << n); i++) {
        for(int j = 0; j < n; j++) {
            if((i >> j) & 1) {
                s[i] += c[j];
                if(__builtin_popcount(i) != 1) {
                    dp[i][j] = inf;
                }
            }
        }
    }
}

struct line{
    ll k, b;
    ll get(ll x) {
        return k * x + b;
    }
};
vector<line> st[N];
vector<array<ll, 2>> f[N];

long double cross(line x, line y) {
    return (1.0 * (x.b - y.b)) / (1.0 * (y.k - x.k));
}
bool check(line x, line y, line z) {
    return (x.b - y.b) * (z.k - y.k) >= (y.b - z.b) * (y.k - x.k);
    // return cross(x, y) >= cross(y, z);
}
void add(int i, line x) {
    if(!st[i].empty() && st[i].back().k == x.k) return;
    while((int)st[i].size() >= 2 && check(st[i][(int)st[i].size() - 2], st[i].back(), x)) {
        st[i].pop_back();
    }
    st[i].push_back(x);
}

ll get(int i, ll x) {
    int l = -1, r = (int)st[i].size() - 1;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(cross(st[i][mid], st[i][mid + 1]) >= x * 1.0) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return st[i][r].get(x);
}
void test() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> c[i];
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            d[i][j] = inf;
        }
        d[i][i] = 0;
    }
    for(int i = 1; i <= m; i++) {
        int a, b, t;    
        cin >> a >> b >> t;
        a--;
        b--;
        d[a][b] = t;
    }
    prec();
    for(int i = 0; i < (1 << n); i++) {
        for(int j = 0; j < n; j++) {
            if((i >> j) & 1) {
                for(int k = 0; k < n; k++) {
                    if(!((i >> k) & 1)) {
                        int nv = (i + (1 << k));
                        if(d[j][k] == inf) continue;
                        dp[nv][k] = min(dp[nv][k], dp[i][j] + s[i] * 1ll * d[j][k]);
                    }
                }
            }
        }
    }
    for(int i = 0; i < (1 << n); i++) {
        for(int j = 0; j < n; j++) {
            if((i >> j) & 1) {
                f[j].push_back({-s[i], dp[i][j]});
            }
        }
    }
    for(int i = 0; i < n; i++) {
        sort(f[i].begin(), f[i].end(), [&](array<ll, 2> x, array<ll, 2> y){
            if(x[0] != y[0]) {
                return x[0] > y[0];
            }
            return x[1] < y[1];
        });
        for(auto [k, b]:f[i]) {
            add(i, {k, b});
        }
    }
    int q;
    cin >> q;

    while(q--) {
        int t, e;
        cin >> t >> e;
        e--;
        ll res = get(e, t);
        cout << -res << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    return 0;
}