//装满的油箱
//这道题应该属于无向图的最短路径问题，采用dijkstra算法，并且每次在求最短路时考虑两种情况：
//1-> if 当前油量+1 < 邮箱容量 那么可以尝试加1升油
//2-> if 当前油量>某一条边的权值 那么可以尝试到达一个新的结点


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

using namespace std;
const int N=1005;
const int M=20005;
const int C=105;

//图的存储结构
int w[M],h[N],e[M],ne[M],idx;// w为边的权值，
int p[N],dist[N][C];// p 存储 price，即每个加油站的油价， dist[u][k]表示在u点，剩余油量为k时所花费的最少油钱。
int n,m;
int st[N][C];// 判重数组

//存储每个点的状态时采用一个三元组
struct node
{
    int d,u,c;// d 存到这个点时最少花费的油钱,u结点编号，c剩余油量
    bool operator <(const node &w)const
    {
        return d>w.d;
    }//重载小于号
};
//加边函数
void add(int a, int b ,int c)
{
    //数组存储邻接表
    idx++;
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
}

int dijkstra(int c,int start,int end)
{
    //c 当前车的油罐容量
    priority_queue<node> heap;
    memset(dist,0x3f,sizeof(dist));
    memset(st,0,sizeof(st));

    node a;
    a.d=0,a.u=start,a.c=0;
    heap.push(a);
    dist[start][0]=0;

    while(!heap.empty())
    {
        //总体思路为拿当前的点 t 来更新 dist数组，维持最小值
        node t=heap.top();
        heap.pop();
        if(t.u==end) return t.d;//判断是否到达终点
        if(st[t.u][t.c]) continue;//该结点入过队 pass
        st[t.u][t.c]=true;

        //第一种情况，如果当前油量没满，可以尝试加一升油
        if(t.c<c)
        {
            //若加一升油后在该结点的花费小于原先的油费，则更新一下数值
            if(dist[t.u][t.c+1]>t.d+p[t.u])
            {
                dist[t.u][t.c+1]=t.d+p[t.u];
                node tem;
                tem.d=dist[t.u][t.c+1],tem.u=t.u,tem.c=t.c+1;
                heap.push(tem);
            }
        }

        //依次遍历当前点能到达的其他点

        for(int i=h[t.u];i;i=ne[i])
        {
            if(t.c>=w[i])
            {
                //若当前剩余油量大于边的权值，则可以到达一个新点

                if(dist[e[i]][t.c-w[i]]>t.d)
                {
                    dist[e[i]][t.c-w[i]]=t.d;
                    node tem;
                    tem.d=t.d,tem.u=e[i],tem.c=t.c-w[i];
                    heap.push(tem);
                }
            }
        }

    }
    return -1;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    cin>>p[i];
    int u,v,d;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>d;
        add(u,v,d),add(v,u,d);
    }

    int query;
    cin>>query;
    int c,s,e;
    while(query--)
    {
        cin>>c>>s>>e;
        int res=dijkstra(c,s,e);
        if(res==-1)
        cout<<"impossible"<<endl;
        else 
        cout<<res<<endl;
    }
    return 0;
}