// Source: USACO 2023 January Contest (Platinum)
// Problem: Mana Collection
#include <bits/stdc++.h>

using LL = long long;
using ULL = unsigned LL;

constexpr ULL E(long double x, int y) {
    while (y--) x *= 10;
    return x;
}
constexpr ULL SIZE(long double x, int y) {return E(x, y) + 5;}

const int inf32 = E(1, 9) + 5;
const LL inf64 = E(1, 18) + 5;
using INT32 = int;
using INT64 = long long;
using INT128 = __int128;

struct Vector2 {
    LL x, y;
    Vector2() = default;
    Vector2(LL _x, LL _y): x(_x), y(_y) {}
    friend INT128 operator*(const Vector2 &a, const Vector2 &b) {return a.x * b.y - a.y * b.x;}
    friend Vector2 operator-(const Vector2 &a, const Vector2 &b) {return {a.x - b.x, a.y - b.y};}
    LL Calc(LL k) {return y - x * k;}
};
struct Maintain {
    int cnt, top;
    Vector2 a[1 << 18], sta[1 << 18];
    void Insert(const Vector2 &x) {a[++cnt] = x;}
    void Build() {
        std::sort(a + 1, a + cnt + 1, [](const Vector2 &a, const Vector2 &b) {return a.x < b.x;});
        for (int i = 1; i <= cnt; i++) {
            while (top > 1 && (sta[top] - sta[top - 1]) * (a[i] - sta[top]) <= 0) top--;
            sta[++top] = a[i];
        }
    }
    LL Query(LL k) {
        int l = 1, r = top - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (sta[mid].Calc(k) <= sta[mid + 1].Calc(k)) r = mid - 1;
            else l = mid + 1;
        }
        return sta[r + 1].Calc(k);
    }
};

int n, m, q;
Maintain ans[20];
LL sum[1 << 18], dis[20][20], f[1 << 18][20];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%lld", &sum[1 << i]);
    for (int i = 1; i < 1 << n; i++) {
        int j = i & -i;
        sum[i] = sum[i ^ j] + sum[j];
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dis[i][j] = inf64;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        dis[x - 1][y - 1] = std::min(dis[x - 1][y - 1], static_cast<LL>(z));
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
    for (int i = 0; i < 1 << n; i++)
        for (int j = 0; j < n; j++)
            f[i][j] = inf64;
    for (int i = 0; i < n; i++) f[1 << i][i] = 0;
    for (int s = 1; s < 1 << n; s++)
        for (int i = 0; i < n; i++) {
            if (f[s][i] == inf64) continue;
            for (int j = 0; j < n; j++) {
                if (s >> j & 1) continue;
                if (dis[i][j] == inf64) continue;
                f[s | 1 << j][j] = std::min(f[s | 1 << j][j], f[s][i] + sum[s] * dis[i][j]);
            }
        }
    for (int s = 1; s < 1 << n; s++)
        for (int i = 0; i < n; i++) {
            if (f[s][i] == inf64) continue;
            ans[i].Insert({sum[s], f[s][i]});
        }
    for (int i = 0; i < n; i++) ans[i].Build();
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int s, e;
        scanf("%d%d", &s, &e);
        printf("%lld\n", -ans[e - 1].Query(s));
    }
    return 0;
}