/*
 * main.cpp
 *
 *  Created on: Sep 17, 2008
 *      Author: Chris
 */

#include <cstdio>
#include <algorithm>

using namespace std;

int cities[81];
int roads[81][81];

int path[81][81];
int feast[81][81];

int num_cities, num_roads, num_queries;

void floyd() {
	for (int k = 1; k <= num_cities; k++) {
		for (int i = 1; i <= num_cities; i++) {
			for (int j = 1; j <= num_cities; j++) {
				if (path[i][k] == -1 || path[k][j] == -1) continue;
				if (path[i][j] == -1
						|| path[i][j] + feast[i][j] > path[i][k] + path[k][j] + max(feast[i][k], feast[k][j])) {
					path[i][j] = path[i][k] + path[k][j];
					feast[i][j] = max(feast[i][k], feast[k][j]);
				}
			}
		}
	}
}

int main() {
	int case_num = 1;

	while(true) {
		scanf("%d %d %d", &num_cities, &num_roads, &num_queries);
		if (num_cities == 0) break;

		if (case_num != 1) printf("\n");

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

		for (int i = 1; i <= num_cities; i++) scanf("%d", cities + i);

		for (int i = 1; i <= num_cities; i++) {
			for (int j = 1; j <= num_cities; j++) {
				path[i][j] = -1;
				feast[i][j] = max(cities[i], cities[j]);
			}
			path[i][i] = 0;
		}


		for (int i = 0; i < num_roads; i++) {
			int a, b, cost;
			scanf("%d %d %d", &a, &b, &cost);
			path[a][b] = path[b][a] = cost;
		}

		floyd(); floyd();

		for (int i = 0; i < num_queries; i++) {
			int s, f;
			scanf("%d %d", &s, &f);
			if (path[s][f] == -1) printf("-1\n");
			else printf("%d\n", path[s][f] + feast[s][f]);
		}
	}


	return 0;
}
