#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 ;

 }