#include<bits/stdc++.h>
using namespace std;
struct node{
	int d;
	int gas;
	int mon;
	friend bool operator <(node a,node b){
		a.mon<b.mon;
	}
};
int n,m;
int a[100005][3],last[1005],len=0;
int p[1005];
int qq;
int flag[1005][105];
void init(){
	for(int i=0;i<n;i++){
		a[i][0]=i;
		a[i][1]=-1;
		a[i][2]=0;
		last[i]=i;
	}
	len=n-1;
}
void f(int x,int id,int z){
	a[len+1][0]=x;
	a[len+1][1]=last[id];
	a[len+1][2]=z;
	last[id]=len+1;
	len++;
}
priority_queue<node> q;
int bfs(int c,int s,int e){
	memset(flag,0,sizeof(flag));
	int i,j; 
	node d1,d2;
	d1.d=s;d1.gas=0;d1.mon=0;
	q.push(d1);
	for(;!q.empty();){
		d1=q.top();q.pop();
		if(flag[d1.d][d1.gas]==1)continue;
		flag[d1.d][d1.gas]=1;
//		cout<<d1.d<<" "<<d1.gas<<" "<<d1.mon<<endl;
		if(d1.d==e){cout<<d1.mon<<endl;return 0;}
		if(d2.gas<c&&!flag[d1.d][d1.gas-1]){
			d2.d=d1.d;d2.gas=d1.gas+1;d2.mon=d1.mon+p[d1.d];
			q.push(d2);
		}
		for(i=last[d1.d];i!=-1;i=a[i][1]){
			if(d1.gas<a[i][2]||flag[d1.d][d1.gas-a[i][2]]==1)continue;
			d2.d=a[i][0];d2.gas=d1.gas-a[i][2];d2.mon=d1.mon;
			q.push(d2);
		}
	}
	cout<<"impossible"<<endl;
}
int main(){
	int i,j;
	cin>>n>>m;
	init();
	for(i=0;i<n;i++){cin>>p[i];}
	for(i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		f(x,y,z);
		f(y,x,z);
	}
	cin>>qq;
	for(i=1;i<=qq;i++){
		int c,s,e;
		cin>>c>>s>>e;
		bfs(c,s,e);
	}
	return 0;
}