#include <cstdio>
#include <cassert>
#include <queue>
#include <cstring>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int, int> P;
#define Fi first
#define pb push_back
#define Se second

const int MAX_N = 1000 + 10;
const int MAX_C = 100 + 10;
int d[MAX_N][MAX_C], n, m, cost[MAX_N], c, Q, s, t;
vector<pair<int, int> >G[MAX_N];

struct node {
    int city, fuel, cost;

    inline bool operator < (const node&x) const {
	return cost > x.cost;
    }
};

priority_queue<node> q;

int main() {
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", cost + i);
    for (int i = 1; i <= m; ++i) {
	int u, v, C;
	scanf("%d%d%d", &u, &v, &C);
	G[u + 1].pb(P(v + 1, C));
	G[v + 1].pb(P(u + 1, C));
    }	

    scanf("%d", &Q);
    while (Q--) {
	scanf("%d%d%d", &c, &s, &t);
	++s, ++t;
	memset(d, -1, sizeof(d));
	while (!q.empty()) q.pop();
	d[s][0] = 0;
	q.push(node {s, 0, 0} );

	bool ok = false;
	while (!q.empty()) {
	    node p = q.top(); q.pop();
//	    assert (q.empty() || d[p.city][p.fuel] <= d[q.top().city][q.top().fuel]);
	    if (p.city == t) {
		printf("%d\n", p.cost);
		ok = true;
		break;
	    }
	    if (d[p.city][p.fuel] < p.cost) continue;
	    if (p.fuel < c && (d[p.city][p.fuel + 1] == - 1 || d[p.city][p.fuel + 1] > d[p.city][p.fuel] + cost[p.city])) {
		d[p.city][p.fuel + 1] = d[p.city][p.fuel] + cost[p.city];
		q.push(node {p.city, p.fuel + 1, d[p.city][p.fuel + 1]} );
	    }

	    for (const auto&i : G[p.city]) {
		if (p.fuel >= i.Se && (d[i.Fi][p.fuel - i.Se] == -1 || d[i.Fi][p.fuel - i.Se] > d[p.city][p.fuel])) {
		    d[i.Fi][p.fuel - i.Se] = d[p.city][p.fuel];
		    q.push(node {i.Fi, p.fuel - i.Se, d[i.Fi][p.fuel - i.Se]});
		}
	    }
	}
	if (!ok) puts("impossible");
    }
    return 0;
}