#include <bits/stdc++.h>
using namespace std;

#define inf 522133279
#define inf_m 31
#define mx 85
#define mx_d 12
int mat[mx][mx], fest[mx][mx];

void floyd(int n)
{
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(mat[i][j] + fest[i][j] > mat[i][k] + mat[k][j] + max(fest[i][k], fest[k][j]))
                {
                    mat[i][j] = mat[i][k] + mat[k][j];
                    fest[i][j] = max(fest[i][k], fest[k][j]);
                }

}

int main()
{
    int i, j, t, kase(0), n, u, v, total, k, m, q, c;
    while(scanf("%d %d %d", &n, &m, &q) && n+m+q)
    {
        if(kase)
            puts("");
        memset(mat, inf_m, sizeof(mat));
        memset(fest, inf_m, sizeof(fest));
        for(i = 1; i <= n; i++)
            scanf("%d", &fest[i][i]), mat[i][i] = 0;
        while(m--)
        {
            scanf("%d %d %d", &u, &v, &c);
            mat[u][v] = mat[v][u] = c;
            fest[u][v] = fest[v][u] = max(fest[u][u], fest[v][v]);
        }
        floyd(n);
        floyd(n);
        printf("Case #%d\n", ++kase);
        while(q--)
        {
            scanf("%d %d", &u, &v);
            mat[u][v] + fest[u][v] >= inf ? puts("-1") : printf("%d\n", mat[u][v] + fest[u][v]);
        }
    }
    return 0;
}