#include<bits/stdc++.h>
#define mod 10000
using namespace std;
int n,m,q;
int t[205];
int  lc[205][205];


int main()
{	
	cin>>n>>m;
	
	for(int i = -1 ; i < n ; i++ )
	{
		for(int j = -1 ; j < n ; j++ )
		{
			lc[i][j]=1e9;
			if(i==j) lc[i][j]=0;
		}
	}
	//初始化
	
	for(int i = 0 ; i <= n-1 ; i++) cin>>t[i];
	
	for(int i = 1 ; i <= m ; i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		lc[a][b]=c;
		lc[b][a]=c;
	}
	//建图 
	
	int now = 0;
	//now用来更新现在第几个村庄修好了 
	cin>>q;
	for(int r = 1 ;r<=q;r++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if( t[a]>c || t[b]>c ) cout<<-1<<"\n"; 	
		else 
		{
			int tmp,noww=now;
			
			if( t[a] <= t[b] ) tmp = b ;
			else tmp = a;
			//tmp是a,b中修好时间较晚的 
			while( t[tmp] <= c)
			{
				tmp++;
				if( tmp == n+1 ) break;
			}
			
			tmp--;
			//更新当时间为c时最晚修好的村庄序号为tmp 
			now = tmp;
				
			for( int k = noww ; k < now ; k++ )//noww是上次更新now的值 ,now是现在时间增加后晚修好的村庄序号（所有noww--now会遍历完一遍k） 
			{
				for(int i=0;i<n;i++)
				{
					for(int j=0;j<n;j++)
					{	
						if( k!=i && k!=j && i!=j )//可能没什么用的特判 
						{
							lc[i][j] = lc[j][i] = min( lc[i][j] , lc[i][k]+lc[k][j]  );
							 
						} 

					}
				}
			}

			if( lc[a][b] > 10000 ) cout<<-1<<endl;
			else  cout<<lc[a][b]<<"\n" ;
		}
		
	}
	return 0;
}