#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 5;
const int M = 1e4 + 5;

int head[N], price[N], cnt, dis[N][100];
bool st[N][100];
struct Edge{
    int v, w, next;
}edge[M << 1];
struct Node{
    int idx, cost, oil;
    bool operator < (const Node& a) const {
        return cost > a.cost;
    }
};

void add(int u, int v, int w)
{
    edge[++cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int dijkstra(int c, int u, int v)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(st, false, sizeof(st));
    priority_queue<Node> heap;
    Node start = {u, 0, 0};
    dis[u][0] = 0;
    heap.push(start);
    while (heap.size())
    {
        Node cur = heap.top();
        heap.pop();
        if (cur.idx == v && !cur.oil) return cur.cost;
        if (st[cur.idx][cur.oil]) continue;
        st[cur.idx][cur.oil] = true;
        if (cur.oil + 1 <= c && dis[cur.idx][cur.oil+1] > cur.cost + price[cur.idx])
        {
            dis[cur.idx][cur.oil+1] = cur.cost + price[cur.idx];
            Node next = {cur.idx, dis[cur.idx][cur.oil+1], cur.oil+1};
            heap.push(next); 
        }
        for (int i = head[cur.idx]; ~i; i = edge[i].next)
        {
            int temp = edge[i].v;
            if (cur.oil >= edge[i].w && dis[temp][cur.oil-edge[i].w] > cur.cost)
            {
                dis[temp][cur.oil-edge[i].w] = cur.cost;
                Node next = {temp, dis[temp][cur.oil-edge[i].w], cur.oil-edge[i].w};
                heap.push(next);
            }
        }
    }
    return -1;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &price[i]);
    memset(head, -1, sizeof (head));
    for (int i = 0; i < m; ++i)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    int q;
    scanf("%d", &q);
    while (q--)
    {
        int c, u, v;
        scanf("%d %d %d", &c, &u, &v);
        int res = dijkstra(c, u, v);
        if (res == -1) puts("impossible");
        else printf("%d\n", res);
    }
//  for (int i = 0; i < n; ++i)
//  {
//      for (int j = 0; j <= 10; ++j)
//      {
//          cout << dis[i][j] << " ";
//      }
//      cout << endl;
//  }
    return 0;
}