#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 400 + 5;

int n, r, dp[N][N][N][2], t[N][2], ans[N][N][N][2], tam;
int a, b, w, z, esc, q;
vector<int> idx[2], aux;

int32_t main(){
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> r;
  for(int i = 1; i <= n; i++) {
    idx[0].push_back(i);
    cin >> t[i][0];
    aux.push_back(t[i][0]);
  }

  sort(idx[0].begin(), idx[0].end(), [](int a, int b) {
      if(t[a][0] == t[b][0]) return a < b;
      return (t[a][0] < t[b][0]);
  });

  idx[1] = idx[0];
  reverse(idx[1].begin(), idx[1].end());

  sort(aux.begin(), aux.end());
  aux.resize(unique(aux.begin(), aux.end()) - aux.begin());
  tam = aux.size();
  for(int i = 1; i <= n; i++) t[i][0] = lower_bound(aux.begin(), aux.end(), t[i][0]) - aux.begin() + 1;
  for(int i = 1; i <= n; i++) t[i][1] = tam - t[i][0] + 1;

  memset(dp, 63, sizeof dp);
  memset(ans, 63, sizeof ans);

  for(int i = 1; i <= n; i++)
    for(int k = 0; k < 2; k++)
      dp[i][i][0][k] = 0;

  for(int i = 1; i <= r; i++){
    cin >> a >> b >> w;
    for(int k = 0; k < 2; k++) dp[a][b][0][k] = dp[b][a][0][k] = w;
  }

  for(int k = 0;  k+1 <= n; k++){
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++){
        for(int p = 0; p < 2; p++){
          int v = idx[p][k];
          dp[i][j][k+1][p] = min(dp[i][j][k][p], dp[i][v][k][p] + dp[v][j][k][p]);
          ans[i][j][t[v][p]][p] = min(ans[i][j][t[v][p]][p], dp[i][j][k+1][p]);
        }
      }
    }
  }

  cin >> q;
  while(q--){
    cin >> a >> b >> z >> esc;
    cout << (ans[a][b][z][esc] == INF ? -1 : ans[a][b][z][esc]) << "\n";
  }
}