#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e3 + 10, M = 1e4 + 10, C = 1e2 + 10;
int dist[N][C];
int idx, e[M<<1], w[M<<1], ne[M<<1], h[N];
bool st[N][C];
int n, m, q, p[N];
struct node {
int point, c, pr;
// friend bool operator < (node a, node b) {
// return a.pr > b.pr;
// }
bool operator < (const node & T) const {
return pr > T.pr;
}
};
inline void ad(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dijkstra (const int C, const int a, const int b) {
priority_queue<node> q;
memset(st, false, sizeof st);
memset(dist, 0x3f, sizeof dist);
q.push((node){a, 0, 0});
dist[a][0] = 0;
while(!q.empty()) {
node now = q.top(); q.pop();
int u = now.point, c = now.c, pr = now.pr;
if(u == b) return pr;
if(st[u][c]) continue;
st[u][c] = true;
if(c < C && dist[u][c + 1] > pr + p[u]) {
dist[u][c + 1] = pr + p[u];
q.push((node){u, c + 1, dist[u][c + 1]});
}
for(int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
if(c >= w[i] && dist[v][c - w[i]] > pr) {
dist[v][c - w[i]] = pr;
q.push((node){v, c - w[i], pr});
}
}
}
return -1;
}
int main (void) {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%d", &p[i]);
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i++) {
int a, b, c; scanf("%d%d%d", &a, &b, &c); ad(a, b, c), ad(b, a, c);
}
scanf("%d", &q);
while(q--) {
int c, a, b; scanf("%d%d%d", &c, &a, &b);
int D = dijkstra(c, a, b);
if(D == -1) printf("impossible\n");
else printf("%d\n", D);
}
return 0;
}