/*******************************
* بسم الله الرحمن الرحيم
* Harunur Rashid
********************************
************Template Starts Here***********/
#include<bits/stdc++.h>
#include <tr1/unordered_set>
#include <tr1/unordered_map>
using namespace std;
using std::tr1::unordered_set;
using std::tr1::unordered_map;
#define endl "\n"
#define eps 1e-9
#define sf scanf
#define xx first
#define yy second
#define pf printf
#define ppb pop_back
#define sqr(x) ((x)*(x))
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define mod 1000000007
#define degree(a) 180.0*a/pi
#define radiun(a) pi*a/180.0
#define pr(a) cout<<a<<"\n"
#define sz(x) ((int)x.size())
#define all(a) a.begin(),a.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define leadingzero(x) __builtin_clz(x)
#define trailingzero(x) __builtin_ctz(x)
#define countbit(x) __builtin_popcount(x)
#define lcm(a,b) (abs(a)/gcd(a,b))*abs(b)
typedef long long int LL;
typedef unsigned long long int LLU;
typedef vector<int> vi;
typedef pair<int,int> pii;
template<class T>
T mod_f(T num)
{
if(num>=0) return num%mod;
else return ((num%mod)+mod)%mod;
}
template<class T>
T fast_pow(T b,T p)
{
if(p==0) return 1;
if(p%2)
{
T x=mod_f(mod_f(b)*mod_f(fast_pow(b,p-1)));
return x;
}
else
{
T x=mod_f(fast_pow(b,p/2));
x=mod_f(mod_f(x)*mod_f(x));
return x;
}
}
template<class T>
T gcd(T a,T b)
{
a=abs(a);
b=abs(b);
while(b)
{
T r=a%b;
a=b;
b=r;
}
return a;
}
template<class T>
LL stoi(T str)
{
stringstream ss(str);
LL N;
ss>>N;
return N;
}
template<class T>
string itos(T N)
{
stringstream ss;
ss<<N;
string ret;
ret=ss.str();
return ret;
}
template<class T>
ostream& operator<<(ostream& out,vector<T>v)
{
int sz=v.size()-1;
for(int i=0; i<=sz; i++) out<<v[i]<<" ";
return out;
}
template<class T>
ostream& operator,(ostream& out,T a)
{
out<<a<<" ";
return out;
}
/* int gcd,x,y;
void extendedEuclid(int A,int B)
{
if(B==0)
{
gcd=A;
x=1;
y=0;
}
else
{
extendedEuclid(B,A%B);
int u=x;
x=y;
y=u-(A/B)*y;
}
}
*/
//bool isEqual(double a,double b) { return fabs(a-b)<=eps; }
//bool isLessThan(double a,double b) { return a+eps<b; }
//bool isLessThanEqual(double a,double b) { return a<b+eps; }
//bool isGreaterThan(double a,double b) { return a>b+eps; }
//bool isGreaterThanEqual(double a,double b) { return a+eps>b; }
//bool Palindrome(string s) { return equal(s.begin(), s.end(), s.rbegin()); }
//int day[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//bool isVowel(char ch){ch=tolower(ch);if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u')return true;return false;}
//bool isUpper(char c){return c>='A' && c<='Z';}
//bool isLower(char c){return c>='a' && c<='z';}
/*/ 4 direction ....
int dx[]= {+0,+1,+0,-1};
int dy[]= {+1,+0,-1,+0};
// 8 direction ....
int dx[]= {+0,+1,+1,+1,+0,-1,-1,-1};
int dy[]= {+1,+1,+0,-1,-1,-1,+0,+1};
// Knight direction...
int dx[] = {+1,+1,+2,+2,-1,-1,-2,-2};
int dy[] = {+2,-2,+1,-1,+2,-2,+1,-1};
*/
/***********Template Ends Here***********/
#define mx 88
LL dist[mx][mx],d[mx][mx],cost[mx];
int main()
{
int node,edge,q,i,j,k,u,v;
LL w;
int kase=1;
while(1)
{
scanf("%d%d%d",&node,&edge,&q);
if(node+edge+q==0) break;
for(i=1; i<=node; i++) scanf("%lld",&cost[i]);
for(i=1; i<=node; i++) for(j=1; j<=node; j++) dist[i][j]=-1;
for(i=1; i<=node; i++) for(j=1; j<=node; j++) if(i==j) dist[i][j]=0;
for(i=1; i<=node; i++) for(j=1; j<=node; j++) d[i][j]=max(cost[i],cost[j]);
for(i=1; i<=edge; i++)
{
scanf("%d%d%lld",&u,&v,&w);
dist[u][v]=dist[v][u]=w;
}
/// Floyd-warshal for first time...
for(k=1; k<=node; k++)
for(i=1; i<=node; i++)
for(j=1; j<=node; j++)
{
if(dist[i][k]==-1 or dist[k][j]==-1) continue;
if(dist[i][j]==-1 or dist[i][j]+d[i][j]>dist[i][k]+dist[k][j]+max(d[i][k],d[k][j]))
{
dist[i][j]=dist[i][k]+dist[k][j];
d[i][j]=max(d[i][k],d[k][j]);
}
}
///Floyd-warshal for second time...
for(k=1; k<=node; k++)
for(i=1; i<=node; i++)
for(j=1; j<=node; j++)
{
if(dist[i][k]==-1 or dist[k][j]==-1) continue;
if(dist[i][j]==-1 or dist[i][j]+d[i][j]>dist[i][k]+dist[k][j]+max(d[i][k],d[k][j]))
{
dist[i][j]=dist[i][k]+dist[k][j];
d[i][j]=max(d[i][k],d[k][j]);
}
}
if(kase!=1) printf("\n");
printf("Case #%d\n",kase++);
while(q--)
{
scanf("%d%d",&u,&v);
w=dist[u][v];
if(w!=-1) w+=d[u][v];
printf("%lld\n",w);
}
}
return 0;
}
LyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioKKiDYqNiz2YUg2KfZhNmE2Ycg2KfZhNix2K3ZhdmGINin2YTYsdit2YrZhQoqIEhhcnVudXIgUmFzaGlkCioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCgoqKioqKioqKioqKipUZW1wbGF0ZSBTdGFydHMgSGVyZSoqKioqKioqKioqLwoKI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGUgPHRyMS91bm9yZGVyZWRfc2V0PgojaW5jbHVkZSA8dHIxL3Vub3JkZXJlZF9tYXA+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp1c2luZyBzdGQ6OnRyMTo6dW5vcmRlcmVkX3NldDsKdXNpbmcgc3RkOjp0cjE6OnVub3JkZXJlZF9tYXA7CgojZGVmaW5lIGVuZGwgICAgICAgIlxuIgojZGVmaW5lIGVwcyAgICAgICAgMWUtOQojZGVmaW5lIHNmICAgICAgICAgc2NhbmYKI2RlZmluZSB4eCAgICAgICAgIGZpcnN0CiNkZWZpbmUgeXkgICAgICAgICBzZWNvbmQKI2RlZmluZSBwZiAgICAgICAgIHByaW50ZgojZGVmaW5lIHBwYiAgICAgICAgcG9wX2JhY2sKI2RlZmluZSBzcXIoeCkgICAgICgoeCkqKHgpKQojZGVmaW5lIG1wICAgICAgICAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgICAgICAgICBwdXNoX2JhY2sKI2RlZmluZSBwaSAgICAgICAgIGFjb3MoLTEuMCkKI2RlZmluZSBtb2QgICAgICAgIDEwMDAwMDAwMDcKI2RlZmluZSBkZWdyZWUoYSkgIDE4MC4wKmEvcGkKI2RlZmluZSByYWRpdW4oYSkgIHBpKmEvMTgwLjAKI2RlZmluZSBwcihhKSAgICAgIGNvdXQ8PGE8PCJcbiIKI2RlZmluZSBzeih4KSAgICAgICgoaW50KXguc2l6ZSgpKQojZGVmaW5lIGFsbChhKSAgICAgYS5iZWdpbigpLGEuZW5kKCkKI2RlZmluZSBtZW0oYSxiKSAgIG1lbXNldChhLGIsc2l6ZW9mKGEpKQojZGVmaW5lIGxlYWRpbmd6ZXJvKHgpIF9fYnVpbHRpbl9jbHooeCkKI2RlZmluZSB0cmFpbGluZ3plcm8oeCkgX19idWlsdGluX2N0eih4KQojZGVmaW5lIGNvdW50Yml0KHgpIF9fYnVpbHRpbl9wb3Bjb3VudCh4KQojZGVmaW5lIGxjbShhLGIpICAgKGFicyhhKS9nY2QoYSxiKSkqYWJzKGIpCgoKdHlwZWRlZiBsb25nIGxvbmcgaW50ICAgICAgICAgIExMOwp0eXBlZGVmIHVuc2lnbmVkIGxvbmcgbG9uZyBpbnQgTExVOwp0eXBlZGVmIHZlY3RvcjxpbnQ+ICAgICAgICAgICAgdmk7CnR5cGVkZWYgcGFpcjxpbnQsaW50PiAgICAgICAgICBwaWk7Cgp0ZW1wbGF0ZTxjbGFzcyBUPgpUIG1vZF9mKFQgbnVtKQp7CiAgICBpZihudW0+PTApIHJldHVybiBudW0lbW9kOwogICAgZWxzZSAgICAgICByZXR1cm4gKChudW0lbW9kKSttb2QpJW1vZDsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4KVCBmYXN0X3BvdyhUIGIsVCBwKQp7CiAgICBpZihwPT0wKSByZXR1cm4gMTsKICAgIGlmKHAlMikKICAgIHsKICAgICAgICBUIHg9bW9kX2YobW9kX2YoYikqbW9kX2YoZmFzdF9wb3coYixwLTEpKSk7CiAgICAgICAgcmV0dXJuIHg7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgVCB4PW1vZF9mKGZhc3RfcG93KGIscC8yKSk7CiAgICAgICAgeD1tb2RfZihtb2RfZih4KSptb2RfZih4KSk7CiAgICAgICAgcmV0dXJuIHg7CiAgICB9Cn0KCnRlbXBsYXRlPGNsYXNzIFQ+ClQgZ2NkKFQgYSxUIGIpCnsKICAgIGE9YWJzKGEpOwogICAgYj1hYnMoYik7CiAgICB3aGlsZShiKQogICAgewogICAgICAgIFQgcj1hJWI7CiAgICAgICAgYT1iOwogICAgICAgIGI9cjsKICAgIH0KICAgIHJldHVybiBhOwp9Cgp0ZW1wbGF0ZTxjbGFzcyBUPgpMTCBzdG9pKFQgc3RyKQp7CiAgICBzdHJpbmdzdHJlYW0gc3Moc3RyKTsKICAgIExMIE47CiAgICBzcz4+TjsKICAgIHJldHVybiBOOwp9Cgp0ZW1wbGF0ZTxjbGFzcyBUPgpzdHJpbmcgaXRvcyhUIE4pCnsKICAgIHN0cmluZ3N0cmVhbSBzczsKICAgIHNzPDxOOwogICAgc3RyaW5nIHJldDsKICAgIHJldD1zcy5zdHIoKTsKICAgIHJldHVybiByZXQ7Cn0KCnRlbXBsYXRlPGNsYXNzIFQ+Cm9zdHJlYW0mIG9wZXJhdG9yPDwob3N0cmVhbSYgb3V0LHZlY3RvcjxUPnYpCnsKICAgIGludCBzej12LnNpemUoKS0xOwogICAgZm9yKGludCBpPTA7IGk8PXN6OyBpKyspIG91dDw8dltpXTw8IiAiOwogICAgcmV0dXJuIG91dDsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4Kb3N0cmVhbSYgb3BlcmF0b3IsKG9zdHJlYW0mIG91dCxUIGEpCnsKICAgIG91dDw8YTw8IiAiOwogICAgcmV0dXJuIG91dDsKfQoKLyogaW50IGdjZCx4LHk7CnZvaWQgZXh0ZW5kZWRFdWNsaWQoaW50IEEsaW50IEIpCnsKICAgIGlmKEI9PTApCiAgICB7CiAgICAgICAgZ2NkPUE7CiAgICAgICAgeD0xOwogICAgICAgIHk9MDsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBleHRlbmRlZEV1Y2xpZChCLEElQik7CiAgICAgICAgaW50IHU9eDsKICAgICAgICB4PXk7CiAgICAgICAgeT11LShBL0IpKnk7CiAgICB9Cn0KKi8KLy9ib29sIGlzRXF1YWwoZG91YmxlIGEsZG91YmxlIGIpIHsgcmV0dXJuIGZhYnMoYS1iKTw9ZXBzOyB9Ci8vYm9vbCBpc0xlc3NUaGFuKGRvdWJsZSBhLGRvdWJsZSBiKSB7IHJldHVybiBhK2VwczxiOyB9Ci8vYm9vbCBpc0xlc3NUaGFuRXF1YWwoZG91YmxlIGEsZG91YmxlIGIpIHsgcmV0dXJuIGE8YitlcHM7IH0KLy9ib29sIGlzR3JlYXRlclRoYW4oZG91YmxlIGEsZG91YmxlIGIpIHsgcmV0dXJuIGE+YitlcHM7IH0KLy9ib29sIGlzR3JlYXRlclRoYW5FcXVhbChkb3VibGUgYSxkb3VibGUgYikgeyByZXR1cm4gYStlcHM+YjsgfQovL2Jvb2wgUGFsaW5kcm9tZShzdHJpbmcgcykgeyByZXR1cm4gZXF1YWwocy5iZWdpbigpLCBzLmVuZCgpLCBzLnJiZWdpbigpKTsgfQovL2ludCBkYXlbXT17MCwzMSwyOCwzMSwzMCwzMSwzMCwzMSwzMSwzMCwzMSwzMCwzMX07Ci8vYm9vbCBpc1Zvd2VsKGNoYXIgY2gpe2NoPXRvbG93ZXIoY2gpO2lmKGNoPT0nYScgfHwgY2g9PSdlJyB8fCBjaD09J2knIHx8IGNoPT0nbycgfHwgY2g9PSd1JylyZXR1cm4gdHJ1ZTtyZXR1cm4gZmFsc2U7fQovL2Jvb2wgaXNVcHBlcihjaGFyIGMpe3JldHVybiBjPj0nQScgJiYgYzw9J1onO30KLy9ib29sIGlzTG93ZXIoY2hhciBjKXtyZXR1cm4gYz49J2EnICYmIGM8PSd6Jzt9CgovKi8gNCBkaXJlY3Rpb24gLi4uLgoKaW50IGR4W109IHsrMCwrMSwrMCwtMX07CmludCBkeVtdPSB7KzEsKzAsLTEsKzB9OwoKLy8gOCBkaXJlY3Rpb24gLi4uLgoKaW50IGR4W109IHsrMCwrMSwrMSwrMSwrMCwtMSwtMSwtMX07CmludCBkeVtdPSB7KzEsKzEsKzAsLTEsLTEsLTEsKzAsKzF9OwoKLy8gS25pZ2h0IGRpcmVjdGlvbi4uLgoKaW50IGR4W10gPSB7KzEsKzEsKzIsKzIsLTEsLTEsLTIsLTJ9OwppbnQgZHlbXSA9IHsrMiwtMiwrMSwtMSwrMiwtMiwrMSwtMX07CiovCgovKioqKioqKioqKipUZW1wbGF0ZSBFbmRzIEhlcmUqKioqKioqKioqKi8KI2RlZmluZSBteCA4OAoKTEwgZGlzdFtteF1bbXhdLGRbbXhdW214XSxjb3N0W214XTsKCmludCBtYWluKCkKewogICAgaW50IG5vZGUsZWRnZSxxLGksaixrLHUsdjsKICAgIExMIHc7CiAgICBpbnQga2FzZT0xOwogICAgd2hpbGUoMSkKICAgIHsKICAgICAgICBzY2FuZigiJWQlZCVkIiwmbm9kZSwmZWRnZSwmcSk7CiAgICAgICAgaWYobm9kZStlZGdlK3E9PTApIGJyZWFrOwoKICAgICAgICBmb3IoaT0xOyBpPD1ub2RlOyBpKyspIHNjYW5mKCIlbGxkIiwmY29zdFtpXSk7CgogICAgICAgIGZvcihpPTE7IGk8PW5vZGU7IGkrKykgZm9yKGo9MTsgajw9bm9kZTsgaisrKSBkaXN0W2ldW2pdPS0xOwogICAgICAgIGZvcihpPTE7IGk8PW5vZGU7IGkrKykgZm9yKGo9MTsgajw9bm9kZTsgaisrKSBpZihpPT1qKSBkaXN0W2ldW2pdPTA7CiAgICAgICAgZm9yKGk9MTsgaTw9bm9kZTsgaSsrKSBmb3Ioaj0xOyBqPD1ub2RlOyBqKyspIGRbaV1bal09bWF4KGNvc3RbaV0sY29zdFtqXSk7CgogICAgICAgIGZvcihpPTE7IGk8PWVkZ2U7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIHNjYW5mKCIlZCVkJWxsZCIsJnUsJnYsJncpOwogICAgICAgICAgICBkaXN0W3VdW3ZdPWRpc3Rbdl1bdV09dzsKICAgICAgICB9CgogICAgICAgIC8vLyBGbG95ZC13YXJzaGFsIGZvciBmaXJzdCB0aW1lLi4uCgogICAgICAgIGZvcihrPTE7IGs8PW5vZGU7IGsrKykKICAgICAgICAgICAgZm9yKGk9MTsgaTw9bm9kZTsgaSsrKQogICAgICAgICAgICAgICAgZm9yKGo9MTsgajw9bm9kZTsgaisrKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmKGRpc3RbaV1ba109PS0xIG9yIGRpc3Rba11bal09PS0xKSBjb250aW51ZTsKICAgICAgICAgICAgICAgICAgICBpZihkaXN0W2ldW2pdPT0tMSBvciBkaXN0W2ldW2pdK2RbaV1bal0+ZGlzdFtpXVtrXStkaXN0W2tdW2pdK21heChkW2ldW2tdLGRba11bal0pKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgZGlzdFtpXVtqXT1kaXN0W2ldW2tdK2Rpc3Rba11bal07CiAgICAgICAgICAgICAgICAgICAgICAgIGRbaV1bal09bWF4KGRbaV1ba10sZFtrXVtqXSk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQoKICAgICAgICAvLy9GbG95ZC13YXJzaGFsIGZvciBzZWNvbmQgdGltZS4uLgoKICAgICAgICBmb3Ioaz0xOyBrPD1ub2RlOyBrKyspCiAgICAgICAgICAgIGZvcihpPTE7IGk8PW5vZGU7IGkrKykKICAgICAgICAgICAgICAgIGZvcihqPTE7IGo8PW5vZGU7IGorKykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpZihkaXN0W2ldW2tdPT0tMSBvciBkaXN0W2tdW2pdPT0tMSkgY29udGludWU7CiAgICAgICAgICAgICAgICAgICAgaWYoZGlzdFtpXVtqXT09LTEgb3IgZGlzdFtpXVtqXStkW2ldW2pdPmRpc3RbaV1ba10rZGlzdFtrXVtqXSttYXgoZFtpXVtrXSxkW2tdW2pdKSkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGRpc3RbaV1bal09ZGlzdFtpXVtrXStkaXN0W2tdW2pdOwogICAgICAgICAgICAgICAgICAgICAgICBkW2ldW2pdPW1heChkW2ldW2tdLGRba11bal0pOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICBpZihrYXNlIT0xKSBwcmludGYoIlxuIik7CiAgICAgICAgcHJpbnRmKCJDYXNlICMlZFxuIixrYXNlKyspOwogICAgICAgIHdoaWxlKHEtLSkKICAgICAgICB7CiAgICAgICAgICAgIHNjYW5mKCIlZCVkIiwmdSwmdik7CiAgICAgICAgICAgIHc9ZGlzdFt1XVt2XTsKICAgICAgICAgICAgaWYodyE9LTEpIHcrPWRbdV1bdl07CiAgICAgICAgICAgIHByaW50ZigiJWxsZFxuIix3KTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gMDsKfQo=