C++ :

#include<bits/stdc++.h>
using namespace std;
const int N=1010,C=110,M=20010;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int price[N];
int dist[N][C]; //储存起点到每个点的距离
bool st[N][C]; //标记每个点是否用过
struct Ver{ //距离排序的结构体
	int d,u,c;
	bool operator<(const Ver& W)const
	{
		return d>W.d;
	}
};
void add(int a,int b,int c) //加边
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra(int start,int end,int cap)
{
	memset(dist,0x3f,sizeof dist); //距离设为无穷大
	memset(st,0,sizeof st); //清空标记
	priority_queue<Ver> heap; //堆优化的dijkstra的小根堆
	heap.push({0,start,0}); //起点入队
	dist[start][0]=0; //初始化起点距离
	while(heap.size())
	{
		Ver t=heap.top(); 
		heap.pop();
		if(t.u==end) return t.d; //找到终点
		if(st[t.u][t.c]) continue; //冗余备份
		st[t.u][t.c]=1;
		if(t.c<cap) //加油
		{
			if(dist[t.u][t.c+1]>t.d+price[t.u])
			{
				dist[t.u][t.c+1]=t.d+price[t.u];
				heap.push({dist[t.u][t.c+1],t.u,t.c+1});
			}
		}
		for(int i=h[t.u];i!=-1;i=ne[i]) //走到下一个加油站
		{
			int j=e[i];
			if(t.c>=w[i]) //油量够了才能走
			{
				if(dist[j][t.c-w[i]]>t.d) //通过当前走到后距离更优
				{
					dist[j][t.c-w[i]]=t.d;
					heap.push({dist[j][t.c-w[i]],j,t.c-w[i]});
				}
			}
		}
	}
	return -1;
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&price[i]);
	}
	for(int i=0;i<m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	int query;
	scanf("%d",&query);
	while(query--)
	{
		int a,b,c;
		scanf("%d%d%d",&c,&a,&b);
		int t=dijkstra(a,b,c);
		if(t==-1) printf("impossible\n");
		else printf("%d\n",t);
	 } 
	return 0;
}