Untitled

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;
const int maxn = 1000 + 10;
int n, m, u, v, d, c, s, e, Q;
int cost[maxn];
int weight[maxn][maxn];
vector<int> adj[maxn];
int dp[maxn][100 + 10];
struct Car {
  int cur, left, costSum;
  bool operator<(const Car &other) const { return costSum > other.costSum; }
};
int dij() {
  if (s == e)
    return 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j <= c; j++)
      dp[i][j] = 1e9;
  priority_queue<Car> pq;
  pq.push(Car{s, 0, 0});
  while (!pq.empty()) {
    auto top = pq.top();
    pq.pop();
    if (dp[top.cur][top.left] < top.costSum)
      continue;
    if (top.cur == e && top.left == 0)
      return dp[top.cur][top.left];
    for (auto i : adj[top.cur]) {
      if (c < weight[top.cur][i])
        continue;
      int j = std::max(top.left, weight[top.cur][i]);
      int max_j = c;
      if (cost[top.cur] >= cost[i]) {
        // Next city is cheaper, we should add just enough to reach to next city
        max_j = j;
      }
      for (; j <= max_j; j++) {
        int OilCost = cost[top.cur] * (j - top.left);
        int temp = j - weight[top.cur][i];
        if (dp[i][temp] > top.costSum + OilCost) {
          dp[i][temp] = top.costSum + OilCost;
          pq.push(Car{i, temp, top.costSum + OilCost});
        }
      }
    }
  }
  return 1e9;
}
int main(int argc, char const *argv[]) {
  while (scanf("%d%d", &n, &m) != EOF) {
    for (int i = 0; i < n; i++) {
      adj[i].clear();
      scanf("%d", &cost[i]);
    }
    for (int i = 0; i < m; i++) {
      scanf("%d%d%d", &u, &v, &d);
      adj[u].push_back(v);
      adj[v].push_back(u);
      weight[u][v] = d;
      weight[v][u] = d;
    }
    scanf("%d", &Q);
    while (Q--) {
      scanf("%d%d%d", &c, &s, &e);
      int res = dij();
      if (res == 1e9)
        printf("impossible\n");
      else
        printf("%d\n", res);
    }
  }
  return 0;
}