TOI17: 1221

#include <bits/stdc++.h>

using namespace std;
const int inf = 1e9;
const int N = 5e2 + 10;
int ar[N], dis[N][N], cnt[N][N];

int main(){

    int n, m, Q;
    scanf("%d %d %d", &n, &m, &Q);

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

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i == j) dis[i][j] = 0;
            else dis[i][j] = ar[i] + ar[j],
                 cnt[i][j] = 1 + 1;
        }
    }

    for(int i=1;i<=m;i++){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        if(w < dis[u][v]) dis[u][v] = dis[v][u] = w,
                          cnt[u][v] = cnt[v][u] = 1 + 1;
    }

    for(int k=1;k<=n;k++){
        for(int u=1;u<=n;u++){
            for(int v=1;v<=n;v++){
                int sum_dis = dis[u][k] + dis[k][v];
                int sum_cnt = cnt[u][k] + cnt[k][v];
                if(sum_dis < dis[u][v])
                    dis[u][v] = dis[v][u] = sum_dis,
                    cnt[u][v] = cnt[v][u] = sum_cnt;
                else if(sum_dis == dis[u][v])
                    cnt[u][v] = cnt[v][u] = max(cnt[u][v], sum_cnt);
            }
        }
    }

    for(int q=1;q<=Q;q++){
        int u, v;
        scanf("%d %d", &u, &v);
        printf("%d %d\n", dis[u][v], cnt[u][v]);
    }

    return 0;
}