#include<bits/stdc++.h>
#define N 18
using namespace std;
const long long inf=1e18;
int n,m,q,sum[1<<N];
long long dis[N][N],f[1<<N][N];
inline void cmin(long long &a,const long long &b) {if(b<a) a=b;}
struct node
{
	int x;long long y;
	inline bool operator<(const node &b)
	{
		return x<b.x || (y && y>b.y);
	}
	inline __int128 operator*(const node &b)
	{
		return (__int128)x*b.y-(__int128)y*b.x;
	}
	inline node operator-(const node &b) {return {x-b.x,y-b.y};}
	inline long long calc(int s) {return y-1ll*x*s;}
};
struct maintain
{
	int top,cnt;
	node a[1<<N],st[1<<N];
	inline void insert(int x,long long y) {a[cnt++]={x,y};}
	inline void solve()
	{
		sort(a,a+cnt);for(int i=0;i<cnt;st[++top]=a[i++])
			while(top>1 && (a[i]-st[top-1])*(a[i]-st[top-2])>=0) --top;
	}
	inline long long query(int s)
	{
		int l=1,r=top;
		while(l<r)
		{
			int mid=(l+r)>>1;
			st[mid].calc(s)<st[mid+1].calc(s)?
				r=mid:l=mid+1;
		}
		return -st[l].calc(s);
	}
}T[N];
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;++i) scanf("%d",sum+(1<<i));
	for(int s=1,t;s<1<<n;++s) t=s&-s,sum[s]=sum[t]+sum[s^t];
	for(int i=0;i<n;++i) for(int j=0;j<n;++j) dis[i][j]=inf;
	for(int i=1,u,v,w;i<=m;++i) scanf("%d %d %d",&u,&v,&w),dis[u-1][v-1]=w;
	for(int i=0;i<n;++i) for(int j=0;j<n;++j)
		for(int k=0;k<n;++k) cmin(dis[j][k],dis[j][i]+dis[i][k]);
	for(int s=0;s<1<<n;++s) for(int i=0;i<n;++i) f[s][i]=inf;
	for(int i=0;i<n;++i) f[1<<i][i]=0;
	for(int s=1;s<1<<n;++s) for(int i=0;i<n;++i) if(f[s][i]!=inf)
		for(int j=0;j<n;++j) if(!(s>>j&1) && dis[i][j]!=inf)
			cmin(f[1<<j|s][j],f[s][i]+dis[i][j]*sum[s]);
	for(int s=1;s<1<<n;++s) for(int i=0;i<n;++i)
		if(f[s][i]!=inf) T[i].insert(sum[s],f[s][i]);
	for(int i=0;i<n;++i) T[i].solve();
	scanf("%d",&q);
	for(int s,e;q--;)
	{
		scanf("%d %d",&s,&e);
		printf("%lld\n",T[e-1].query(s));
	}
	return 0;
}