$\text{这里的状态转移比较特殊}$
$\text{在每一个节点 } u, \text{加油，必须一升一升加}$

$$ \textbf{state}(u, gas, cost) $$

$$ x(u, g a s, cost) \rightarrow\left\\{\\begin{array}{l} x(u, g a s+1, cost+p(u)) && g a s+1 \leqslant c \\\ x((u \rightarrow v), g a s-w(u, v), cost) && g a s-w(u, v) \geqslant 0 \end{array}\\right. $$

$\textbf{algorithm}$
$\text{run } dijkstra()$
$\quad \quad \textbf{vis}(u, gas) = 1\text{ , mark node complete}$

const int inf = 0x3f3f3f3f;
const int maxn = 1000 + 10;
int n, m;
int P[maxn];

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
    int from, to, weight;
    Edge() {}
    Edge(int u, int v, int w) : from(u), to(v), weight(w) {}
};

vector<Edge> edges;

void initG() {
    _for(i, 0, maxn) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(u, v, w));
    G[u].push_back(edges.size() - 1);
}
// == Graph finished ==

// == Dijkstra ==
class State {
public:
    int u, gas, cost;
    bool operator< (const State& rhs) const {
        return cost > rhs.cost;
    }

    State() {}
    State(int u, int g, int c) : u(u), gas(g), cost(c) {}
};

int vis[maxn][maxn];
int ans = inf;

void initDij(int st, const int C) {
    Set(vis, 0);
    ans = inf;
}

bool dijkstra(int st, int ed, const int C) {
    initDij(st, C);
    priority_queue<State> que;
    que.push(State(st, 0, 0));

    while (!que.empty()) {
        State x = que.top();
        que.pop();

        if(x.u == ed) {
            ans = x.cost;
            return true;
        }

        if(vis[x.u][x.gas]) continue;
        vis[x.u][x.gas] = 1;

        if(x.gas + 1 <= C) {
            State nxt(x.u, x.gas + 1, x.cost + P[x.u]);
            que.push(nxt);
        }
        _for(i, 0, G[x.u].size()) {
            const Edge& e = edges[G[x.u][i]];
            int y = e.to;

            if(x.gas >= e.weight) {
                State nxt(y, x.gas - e.weight, x.cost);
                que.push(nxt);
            }
        }
    }
    return false;
}
// == Dijkstra finsihed ==

void init() {
    Set(P, 0);
}

void solve() {
    int q;
    scanf("%d", &q);
    while (q--) {
        int st, ed, C;
        scanf("%d%d%d", &C, &st, &ed);
        if(dijkstra(st, ed, C)) printf("%d\n", ans);
        else printf("impossible\n");
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    initG();
    init();
    // get data
    _for(i, 0, n) scanf("%d", &P[i]);
    _for(i, 0, m) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    // each query, dijkstra
    solve();
}