> #include<stdio.h>
> #include<string.h>
> #include<stdlib.h>
> #include<iostream>
> #include<algorithm>
> using namespace std;
> #define M 1010
> int n,m,tot,head[M*2],mark[M],mm[M],Q[M*M];
> __int64 dis[M][M];
> __int64 oo,kk;
> struct node
> {
> 	int to,next;
> 	__int64 cost;
> }edge[M*100];
> struct rest
> {
> 	__int64 val;
> 	int n;
> }res[M];
> bool cmp(rest a,rest b)
> {
> 	return a.val>b.val;
> }
> int add(int a,int b,__int64 c)
> {
> 	edge[tot].to=b;edge[tot].cost=c;edge[tot].next=head[a];head[a]=tot++;
> 	edge[tot].to=a;edge[tot].cost=c;edge[tot].next=head[b];head[b]=tot++;
> 	return 0;
> }
> int spfa(int x,__int64 xx)
> {
> 	int i,j;
> 	for(i=1;i<=n;i++)
> 	{
> 		if(!mm[i])
> 		{
> 			dis[x][i]=oo;
> 		}
> 		mark[i]=0;
> 	}
> 	int l,r;
> 	l=r=0;
> 	Q[r++]=x;
> 	mark[x]=1;
> 	dis[x][x]=xx;
> 	
> 	while(l<r)
> 	{
> 		int u=Q[l++];
> 		if(!mm[u])mark[u]=0;//printf("****\n");
> 		for(i=head[u];i!=-1;i=edge[i].next)
> 		{
> 			int y=edge[i].to;
> 			if(mm[y]&&!mark[y])
> 			{
> 				dis[x][y]=dis[y][x];
> 				Q[r++]=y;
> 				mark[y]=1;
> 				continue;
> 			}
> 			else if(dis[x][u]+edge[i].cost<dis[x][y])
> 			{
> 				dis[x][y]=dis[x][u]+edge[i].cost;
> 				if(!mark[y])Q[r++]=y,mark[y]=1;
> 			}
> 		}
> 	}
> 	return 0;
> }
> 
> 
> int main()
> {
> 	int i,j;
> 	kk=2000000010;
> 	oo=kk*200100;
> 	//cout<<oo<<endl;
> 	while(scanf("%d%d",&n,&m))
> 	{
> 		if(n==0&&m==0)break;
> 		for(i=0;i<n;i++)
> 		{
> 			res[i].n=i+1;
> 			scanf("%I64d",&res[i].val);
> 			//val[i+1]=res[i].val;
> 		}
> 		sort(res,res+n,cmp);
> 		memset(head,-1,sizeof(head));
> 		memset(mm,0,sizeof(mm));
> 		int a,b;
> 		__int64 c;
> 		tot=0;
> 		while(m--)
> 		{
> 			scanf("%d%d%I64d",&a,&b,&c);
> 			add(a,b,c);
> 		}
> 		for(i=0;i<n;i++)
> 		{
> 			
> 			mm[res[i].n]=1;
> 			spfa(res[i].n,res[i].val);
> 			for(j=0;j<i;j++)
> 			dis[res[i].n][res[j].n]=dis[res[j].n][res[i].n];
> 		//	printf("**");		
> 		}
> 		int pro;
> 		/*for(i=1;i<=n;i++)
> 		{
> 			for(j=1;j<=n;j++)
> 			printf("%I64d ",dis[i][j]);
> 			printf("\n");
> 		}*/
> 		scanf("%d",&pro);
> 		while(pro--)
> 		{
> 			scanf("%d%d",&a,&b);
> 			if(dis[a][b]<oo)printf("%I64d\n",dis[a][b]);
> 			else printf("-1\n");
> 		}
> 		printf("\n");
> 	}
> }
> /*
> 6 7
> 1 2 3 4 5 6
> 1 2 1
> 2 3 2
> 3 4 3
> 4 5 4
> 1 5 5
> 2 5 2
> 1 4 3
> 5
> 1 4
> 2 3
> 1 5
> 3 5
> 1 6
> 2 1
> 10 20
> 1 2 5
> 1
> 1 2
> 0 0
> */