emm

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1010,M=10010;//定义数组用 
int head[N],nxt[M<<1],to[M<<1],w[M<<1],tot;//链式前向星存图用;
int n,m,q;
int val[N];//每个城市的油价 
int c,s,e;//每次询问给出的容量，起点，终点；
int v[N][110],dist[N][110];//v数组表示某状态是否入过堆，dist数组表示到达此状态当前搜索到的最小花费 
struct edge{
	int dis; //当前油费
	int x;//当前所处位置
	int c;//当前油量 
};//定义结构体方便表示状态 
bool operator<(const edge &a,const edge &b)
{
	return a.dis>b.dis;
}//重载运算符，根据油费排列小根堆，不会写小根堆的参数qwq 
void add(int x,int y,int c)
{
	to[++tot]=y;
	w[tot]=c;
	nxt[tot]=head[x];
	head[x]=tot;
}//加边函数 
int dijkstra(int c,int start,int end)//c表示油箱容量（油量的最大值），start记录出发点， end记录目标点 
{ 
	priority_queue<edge>que;  
	memset(dist,0x3f,sizeof(dist));//多次询问，需要初始化，要 /求最小值，初始化成极大值 
	memset(v,0,sizeof(v));//初始化 
	que.push((edge){0,start,0});//还是初始化，ps：油箱初始为空 
	dist[start][0]=0;
	while(que.empty()!=1)
	{
		edge q=que.top();//是堆 ，用top（）而不是front（）； 
		que.pop();//不加pop（）见祖宗； 
		if(q.x==end&&q.c==0)return q.dis;//由于是根据dis（油费） 排列的小根堆，且无负边权，搜索到的第一个到达目标点的即为最优解 
		if(v[q.x][q.c])continue;//emmm，原因同上 ，就不用再搜了 
		v[q.x][q.c]=1;//改v留下证据：已搜过 
		if(q.c<c)//油箱没满，加一升 
		{
			if(dist[q.x][q.c+1]>q.dis+val[q.x])
			{
				dist[q.x][q.c+1]=q.dis+val[q.x];
				que.push((edge){q.dis+val[q.x],q.x,q.c+1});	
			}//更新后入堆 
		}
		for(int i=head[q.x];i;i=nxt[i])
		{
			int y=to[i];
			if(q.c>=w[i])//油足够跑到下一座城市 
			{
				if(dist[y][q.c-w[i]]>q.dis)
				{
					dist[y][q.c-w[i]]=q.dis;
					que.push((edge){q.dis,y,q.c-w[i]});
				}//更新后入堆 
			}
		}
	}
	return -1;//一顿搜索没找到，返回-1； 
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>val[i];//从0编号 
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);//无向图双向建边； 
	}
	cin>>q;
	while(q--)//多组询问； 
	{
		cin>>c>>s>>e;
		int t=dijkstra(c,s,e); 
		if(t==-1)
		{
			cout<<"impossible"<<endl;
		}
		else cout<<t<<endl;
	}
	return 0;
}