#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,q;
ll a[20];
ll dis[20][20];
ll sum[1<<18];
ll dp[1<<18][20];
struct line{
	ll k,b;
	__int128 getval(ll x){return (__int128)k*x+b;}
};
struct node{
	line L[1<<18];
	int tree[1<<20],ch[1<<20][2],tot,rt;
	void insert(int &k,ll l,ll r,int x){
		if(!k)k=++tot;
		if(!tree[k]){tree[k]=x;return;}
		ll mid=l+r>>1;
		if(L[tree[k]].getval(mid)<L[x].getval(mid))swap(tree[k],x);
		if(L[tree[k]].getval(l)<L[x].getval(l))insert(ch[k][0],l,mid-1,x);
		else if(L[tree[k]].getval(r)<L[x].getval(r))insert(ch[k][1],mid+1,r,x);
	}
	ll query(int k,ll l,ll r,ll x){
		if(!k)return 0;
		ll mid=l+r>>1,res=L[tree[k]].getval(x);
		if(x<mid)res=max(res,query(ch[k][0],l,mid-1,x));
		else if(x>mid)res=max(res,query(ch[k][1],mid+1,r,x));
		return res;
	}
	void build(int S){
		for(int sta=0;sta<(1<<n);sta++)
			if(sta&(1<<S-1))if(dp[sta][S]<0x3f3f3f3f3f3f3f3f){
				L[sta]=(line){sum[sta],-dp[sta][S]};
				insert(rt,1,1e9,sta);
			}
	}
}T[20];
int main(){
	scanf("%d%d",&n,&m);
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;i++)dis[i][i]=0,scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		dis[x][y]=z;
	}
	for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	for(int sta=0;sta<(1<<n);sta++)for(int i=1;i<=n;i++)if(sta&(1<<i-1))sum[sta]+=a[i];
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++)dp[1<<i-1][i]=0;
	for(int sta=0;sta<(1<<n);sta++)
		for(int i=1;i<=n;i++)if(dp[sta][i]<0x3f3f3f3f3f3f3f3f)
			for(int j=1;j<=n;j++)if(!(sta&(1<<j-1))&&dis[i][j]<0x3f3f3f3f3f3f3f3f)
				dp[sta|(1<<j-1)][j]=min(dp[sta|(1<<j-1)][j],dp[sta][i]+dis[i][j]*sum[sta]);
	for(int i=1;i<=n;i++)T[i].build(i);
	scanf("%d",&q);
	while(q--){
		int s,e;scanf("%d%d",&s,&e);
		printf("%lld\n",T[e].query(T[e].rt,1,1e9,s));
	}
	return 0;
}