C++ :

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
const int N = 1002;
const int M = 20002;
const int C = 101;
int n,m;
int price [N];
struct EDGE{
	int next;
	int to;
	int len;
}edge[M];
struct NODE{
	int dis;
	int pos;
	int c;
	bool operator< (const NODE &x)const
	{
		return x.dis<dis;
	}
};
int head[N];
int dist[N][C];
bool vis[N][C];
int cnt = 0;
inline int read(){
	int f=1,x=0;
	char s=getchar();
	while(s<'0' || s>'9'){
		if(s=='-')
			f=-1;
		s=getchar();
	}
	while(s>='0' && s<='9'){
		x=x*10+s-'0';
		s=getchar();
	}
	return x*f;
}
inline void add_edge(int x,int y,int len)
{
	edge[++cnt].len = len;
	edge[cnt].to = y;
	edge[cnt].next = head[x];
	head[x] = cnt;
}
inline int dijkstra(int c,int start,int end)
{

	memset(vis,0,sizeof(vis));
	memset(dist,0x3f,sizeof dist);
	dist[start][0] = 0;
	priority_queue <NODE> q;
	q.push((NODE){0,start,0});
	while(!q.empty())
	{
		NODE t = q.top();
		q.pop();
		if(t.pos == end)
			return dist[t.pos][t.c];
		if(vis[t.pos][t.c])
			continue ;
		vis[t.pos][t.c] = 1;
		if(t.c<c && dist[t.pos][t.c + 1] > t.dis + price[t.pos])
		{
			dist[t.pos][t.c+1] = t.dis + price[t.pos];
			q.push((NODE){dist[t.pos][t.c+1],t.pos,t.c+1});
		}
		for(register int i=head[t.pos];i;i=edge[i].next)
		{
			register int y = edge[i].to;
			register int w = edge[i].len;
			if(t.c>=w)
			{
				if(dist[y][t.c-w] > t.dis)
				{
					dist[y][t.c-w] = t.dis;
					q.push((NODE){t.dis,y,t.c-w});
				}
			}
		}
	}
	return -1;
}
int main()
{
	n=read(),m=read();
	for(int i=0;i<n;i++)
		price[i] = read();
	for(register int i=1;i<=m;i++)
	{
		int x,y,len;
		x=read(),y=read(),len=read();
		add_edge(x,y,len);
		add_edge(y,x,len);
	}
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int start,capacity,end;
		capacity=read(),start=read(),end=read();
		register int t = dijkstra(capacity,start,end);
		if(t==-1)
			puts("impossible");
		else
			printf("%d\n",t);
	}
	return 0;
}