#include<bits/stdc++.h>
#define MAXM 20005
#define MAXN 205
using namespace std;
int q, n, m, t[MAXN], f[MAXN][MAXN], e[MAXN][MAXN], u, v, w, x[50005], y[50005], tim[50005];

int main(){
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> t[i];
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= n; j ++) f[i][j] = 0x3f3f3f3f;
	for(int i = 1; i <= m; i ++){
		cin >> u >> v >> w;
		f[++u][++v] = w;
	}
	cin >> q;
	for(int i = 1; i <= q; i ++){
		cin >> x[i] >> y[i] >> tim[i];
		++x[i], ++y[i];
	}
	int ptr = 1;  // q
	for(int k = 1; k <= n; k ++){
		while(tim[ptr] < t[k]){//output
			if(f[x[ptr]][y[ptr]] == 0x3f3f3f3f || (tim[ptr] < t[x[ptr]] || tim[ptr] < t[y[ptr]])) cout << "-1\n";
			else cout << f[x[ptr]][y[ptr]] << '\n';
			++ptr;
		}
		for(int i = 1; i <= n; i ++)//floyd
			for(int j = 1; j <= n; j ++)
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
	}
	for(; ptr <= q; ++ptr){
		if(f[x[ptr]][y[ptr]] == 0x3f3f3f3f || (tim[ptr] < t[x[ptr]] || tim[ptr] < t[y[ptr]])) cout << "-1\n";
		else cout << f[x[ptr]][y[ptr]] << '\n';
	}
	return 0;
}