Floyd神用法。。。设dis[i][j]表示i点到j点的最短路（只算边权），map[i][j]表示i到j最小费用
将n个点先按照点权排一下序。。。这样就可以比较方便的求出路径上最大点权了。。。
因为floyd会枚举到路径上的所有节点（当然也包括最短路径外的= =）所以每次找到松弛节点就尝试着更新一下map（最短路不一定费用最少）。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
struct point{
int pos,val;
}poi[maxn];
int ans[],dis[maxn][maxn],map[maxn][maxn];
int i,j,k,n,m,K,tot,a,b,d,num;
int ra;char rx;
inline int read(){
rx=getchar();ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
bool cmp(point a,point b){return a.val<b.val;}
int main(){
n=read();m=read();K=read();
for(i=;i<=n;i++)poi[i].val=read(),poi[i].pos=i;
sort(poi+,poi++n,cmp);
for(i=;i<=n;i++)memset(dis[i],,(n+)<<),memset(map[i],,(n+)<<),dis[i][i]=;
for(i=;i<=m;i++)a=read(),b=read(),d=read(),dis[b][a]=dis[a][b]=min(dis[a][b],d);
for(k=,d=poi[k].pos;k<=n;k++,d=poi[k].pos)
for(i=,a=poi[i].pos;i<=n;i++,a=poi[i].pos)for(j=,b=poi[j].pos;j<=n;j++,b=poi[j].pos){
if(dis[a][d]+dis[d][b]<dis[a][b])dis[a][b]=dis[a][d]+dis[d][b];
map[a][b]=min(map[a][b],dis[a][b]+poi[max(i,max(j,k))].val);
}
for(i=;i<=K;i++)a=read(),b=read(),printf("%d\n",map[a][b]);
return ;
}