#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,f[260][260],a1,a2,a3,ans[260][260],a[260],q;
struct hs{int s,x;}b[260];
bool bk(hs b1,hs b2){return b1.s<b2.s;}
int main(){
	freopen("toll.in","r",stdin);
	freopen("toll.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j)
				f[i][j]=ans[i][j]=999999;
	for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i].s=a[i];b[i].x=i;}
	for(int i=1;i<=m;i++){
	    scanf("%d%d%d",&a1,&a2,&a3);
		f[a1][a2]=min(f[a1][a2],a3);
		f[a2][a1]=f[a1][a2];
	}
	sort(b+1,b+1+n,bk);
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=min(f[i][j],f[i][b[k].x]+f[b[k].x][j]),ans[i][j]=min(ans[i][j],f[i][j]+max(max(a[i],a[j]),a[b[k].x]));
	while(q--){
	    scanf("%d%d",&a1,&a2);
		printf("%d\n",ans[a1][a2]);
	}
	return 0;
}