using namespace std;

int n,m;

int dp[1000][1000];

struct node{

	int to;
	int w1;
};
vector<node> edge[1000];
  
int shu[1000];
  
int main()
  
{
  
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>shu[i];
		for(int j=0;j<n;j++)
		{
			if(i!=j)
			{
				dp[i][j]=1e8;
			}
			else
			{
				dp[i][j]=0;
			}
		}
	}
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		dp[u][v]=w;
		dp[v][u]=w;
	//	edge[u].push_back({v,w});
	//	edge[v].push_back({u,w});
	}
	int q;
	cin>>q;
	while(q--)
	{
		int x,y,t;
		cin>>x>>y>>t;
		int bo=0;
		for(int k=0;k<n;k++)//中转点 
		{
			if(shu[k]>t)
			{
				bo++;
			}
			else
			{
				for(int i=0;i<n;i++)//起点 
			 	{
			 		for(int j=0;j<n;j++)//终点 
			 		{
			 			dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			 		//	cout<<dp[i][j]<<" ";
			 		}
			 	}
			}
			
		} 
		if(bo==t)
		{
			cout<<-1<<endl;
		}
		else
		{
			cout<<dp[x][y]<<endl;
		}
	}
	return 0;
}