//https://www.luogu.com.cn/problem/P1119?contestId=96617
//所有與未重建完成的村莊的公路均無法通車。換句話說，只有連接著兩個重建完成的村莊的公路才能通車
//只有兩個村莊都建好了才可以賦邊權(quán)
#include<bits/stdc++.h>
#define inf 1e9
using namespace std;
int n,m;
int t[200];
int G[200][200];
int Q;
int tt;
int midG[200][200];
struct Node
{
? ?int u;
? ?int v;
? ?int ttt;
};
Node Ques[50000];

bool visited[200];
int ?dist[200];
int dijsktra(int start,int end)
{
? ?fill(visited,visited+200,false);
? ?fill(dist,dist+200,inf);
? ?dist[start]=0;
? ?for(int i=0;i<n;i++)
? ?{
? ? ? ?int u=-1;
? ? ? ?int min=inf;
? ? ? ?for(int j=0;j<n;j++)
? ? ? ?{
? ? ? ? ? ?if(visited[j]==false&&dist[j]<min)
? ? ? ? ? ?{
? ? ? ? ? ? ? ?u=j;
? ? ? ? ? ? ? ?min=dist[j];
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?if(u==-1) return -1;
? ? ? ?visited[u]=true;
? ? ? ?for(int j=0;j<n;j++)
? ? ? ?{
? ? ? ? ? ?if(visited[j]==false&&midG[u][j]!=inf&&dist[j]>dist[u]+midG[u][j])
? ? ? ? ? ?{
? ? ? ? ? ? ? ?dist[j]=dist[u]+midG[u][j];
? ? ? ? ? ?}
? ? ? ?}
? ?}
? ?return dist[end];
}

int main()
{
? ?cin>>n>>m;
? ?for(int i=0;i<n;i++)
? ? ? ?cin>>t[i];
? ?fill(G[0],G[0]+200*200,inf);
? ?for(int i=0;i<n;i++)
? ? ? ?G[i][i]=0;
? ?for(int i=0;i<m;i++)
? ?{
? ? ? ?int u,v,w;
? ? ? ?cin>>u>>v>>w;
? ? ? ?G[u][v]=G[v][u]=w;
? ?}
? ?cin>>Q;
? ?for(int i=0;i<Q;i++)
? ?{
? ? ? ?int u,v,ttt;
? ? ? ?cin>>u>>v>>ttt;
? ? ? ?Ques[i].u=u;
? ? ? ?Ques[i].v=v;
? ? ? ?Ques[i].ttt=ttt;
? ?}
? ?fill(midG[0],midG[0]+200*200,inf);
? ?for(int i=0;i<n;i++)
? ? ? ?midG[i][i]=0;
? ?for(tt=0;tt<=t[n-1];tt++)
? ?{
? ? ? ?//隨時間推移midG中的邊逐漸增加
? ? ? ?//如果某個tt時刻i號村子修好了那么釋放所有到i或者從i出發(fā)的邊
? ? ? ?//如果出現(xiàn)tt時刻的詢問則查詢最短路
? ? ? ?for(int i=0;i<n;i++)
? ? ? ?{
? ? ? ? ? ?if(t[i]<=tt)
? ? ? ? ? ?{

? ? ? ? ? ? ? ?//在tt時刻則說明重建時間小于tt的所有村莊都建好了
? ? ? ? ? ? ? ?//其中最大的tt[i]的村莊編號為i
? ? ? ? ? ? ? ?for(int x=0;x<=i;x++)
? ? ? ? ? ? ? ? ? ?for(int y=0;y<=i;y++)
? ? ? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ? ?midG[x][y]=G[x][y];
? ? ? ? ? ? ? ? ? ? ? ?midG[y][x]=G[y][x];
? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?//查詢在tt時刻是否有存在詢問
? ? ? ?for(int i=0;i<Q;i++)
? ? ? ?{
? ? ? ? ? ?if(Ques[i].ttt==tt)
? ? ? ? ? ?{
? ? ? ? ? ? ? ?int start=Ques[i].u;
? ? ? ? ? ? ? ?int end ?=Ques[i].v;
? ? ? ? ? ? ? ?//執(zhí)行dijsktra
? ? ? ? ? ? ? ?int ans=dijsktra(start,end);
? ? ? ? ? ? ? ?cout<<ans<<endl;
? ? ? ? ? ?}
? ? ? ?}
? ?}
? ?return 0;
}
//為什么連樣例都沒過只有一個沒過了