#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int maxN=10005,inf=0x3f3f3f3f;//maxN改成1005就re~,否则ac
struct node
{
	int id,dis,res;
	
	node(int _id,int _dis,int _res):id(_id),dis(_dis),res(_res){}

	bool operator <(const node &b)const
	{
		return dis>b.dis;
	}
};
struct arc
{
	int id,dis;

	arc(int _id,int _dis):id(_id),dis(_dis){}
};
vector<arc> g[maxN];
int n,m,p[maxN],q,c,s,e,dp[maxN][105];

void read()
{
	scanf("%d%d",&n,&m);
	for (int i = 0; i < n; i++)	scanf("%d",&p[i]);
	while (m--)
	{
		int u,v,d;
		scanf("%d%d%d",&u,&v,&d);
		g[u].push_back(arc(v,d)),g[v].push_back(arc(u,d));
	}
}

int astar()
{
	for(int i=0;i<n;i++)
        for(int j=0;j<=100;j++)
        dp[i][j]=inf;
	dp[s][0]=0;	
	priority_queue<node> pq;
	pq.push(node(s,0,0));
	while (!pq.empty())
	{
		node top=pq.top();
		pq.pop();		
		if (top.id==e) return top.dis; 
		if (top.res+1<=c&&dp[top.id][top.res+1]>dp[top.id][top.res]+p[top.id])
		{
			dp[top.id][top.res+1]=dp[top.id][top.res]+p[top.id];
			pq.push(node(top.id,dp[top.id][top.res+1],top.res+1));
		}
		for (int i = 0; i < g[top.id].size(); i++)
		{
			arc nxt=g[top.id][i];
			if (top.res>=nxt.dis&&dp[nxt.id][top.res-nxt.dis]>top.dis)
			{
				dp[nxt.id][top.res-nxt.dis]=top.dis;
				pq.push(node(nxt.id,top.dis,top.res-nxt.dis));
			}
		}
	}
	return -1;
}

void solve()
{
	scanf("%d",&q);
	while (q--)
	{
		scanf("%d%d%d",&c,&s,&e);
		int t=astar();
		if (~t) printf("%d\n",t);
		else puts("impossible");
	}
}

int main()
{
//	freopen("D:\\input.txt","r",stdin);
	read();
	solve();
	return 0;
}