#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 #define inf 1<<30

 struct Edge{

     int v,w;

     Edge(){}

     Edge(int vv,int ww):v(vv),w(ww){}

 };

 vector<vector<Edge> >g;

 int cost[],dist[],dp[][];

 bool mark[];

 int n,m,Q;

 void spfa(int s)

 {

     memset(mark,false,sizeof(mark));

     fill(dist,dist+n+,inf);

     dist[s]=;

     queue<int>que;

     que.push(s);

     while(!que.empty()){

         int u=que.front();

         que.pop();

         mark[u]=false;

         for(int i=;i<g[u].size();i++){

             int v=g[u][i].v,w=g[u][i].w;

             if(dist[u]+w<dist[v]&&cost[v]<=cost[s]){

                 dist[v]=dist[u]+w;

                 if(!mark[v]){

                     mark[v]=true;

                     que.push(v);

                 }

             }

         }

     }

     for(int i=;i<=n;i++)dp[s][i]=dist[i];

 }

 int main()

 {

     int u,v,w,t=;

     while(~scanf("%d%d%d",&n,&m,&Q)){

         if(n==&&m==&&Q==)break;

         for(int i=;i<=n;i++)scanf("%d",&cost[i]);

         g.clear();

         g.resize(n+);

         while(m--){

             scanf("%d%d%d",&u,&v,&w);

             g[u].push_back(Edge(v,w));

             g[v].push_back(Edge(u,w));

         }

         for(int i=;i<=n;i++)

             for(int j=;j<=n;j++)dp[i][j]=inf;

         for(int i=;i<=n;i++)spfa(i);

         if(t)puts("");

         printf("Case #%d\n",++t);

         while(Q--){

             scanf("%d%d",&u,&v);

             int ans=inf;

             for(int i=;i<=n;i++){

                 if(dp[i][u]==inf||dp[i][v]==inf)continue;

                 ans=min(ans,dp[i][u]+dp[i][v]+cost[i]);

             }

             if(ans==inf)ans=-;

             printf("%d\n",ans);

         }

     }

     return ;

 }