10246

#include <iostream>

#define INF 100000000

using namespace std;

int graph[85][85];
int feast[85][85];


int main()
{
	int C,R,Q;
	int a,b,c;
	int kase=0;

	while(cin>>C)
	{
		cin>>R>>Q;

		if(C==0 && R==0 && Q==0)
		break;

		for(int i=1;i<=C;i++)
		{
			for(int j=1;j<=C;j++)
			{
				if(i==j)
				graph[i][j] = 0;
				else
				graph[i][j] = feast[i][j]=INF;

			}

		}

		for(int i=1;i<=C;i++)
		{
			int g;
			cin>>g;
			feast[i][i]=g;
		}


		for(int i=1;i<=R;i++)
		{
			cin>>a>>b>>c;
			graph[a][b]=c;
			graph[b][a]=c;
			feast[a][b]= feast[b][a] = max(feast[a][a],feast[b][b]);
		}


		for(int k=1;k<=C;k++)
		{
			for(int i=1;i<=C;i++)
			{
				for(int j=1;j<=C;j++)
				{
					if(graph[i][j]+feast[i][j]>graph[i][k]+graph[k][j]+max(feast[i][k],feast[k][j]))
					{
						graph[i][j] = graph[i][k]+graph[k][j];
						feast[i][j] = max(feast[i][k],feast[k][j]);
					}

				}
			}
		}

		for(int k=1;k<=C;k++)
		{
			for(int i=1;i<=C;i++)
			{
				for(int j=1;j<=C;j++)
				{
					if(graph[i][j]+feast[i][j]>graph[i][k]+graph[k][j]+max(feast[i][k],feast[k][j]))
					{
						graph[i][j] = graph[i][k]+graph[k][j];
						feast[i][j] = max(feast[i][k],feast[k][j]);
					}

				}
			}
		}
		if(kase)
		cout<<"\n";
		cout<<"Case #"<<++kase<<"\n";
		for(int i=1;i<=Q;i++)
		{
			cin>>a>>b;
			if(graph[a][b]+feast[a][b]>=INF)
			cout<<-1<<"\n";
			else
			cout<<graph[a][b]+feast[a][b]<<"\n";
			//cout<<graph[a][b];
		}
	}

	return 0;
}