algo2017_week6_networkingrouting

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fo(n) for(int i=0;i<n;i++)
#define MAX 300

int d[MAX][MAX] , n , v , t , node[MAX];


void floyd_warshall(){
    fo( n )
        for( int j = 0 ; j < n ; ++j )
            for( int k = 0 ; k < n ; ++k )
                d[i][j] = d[i][j] > d[i][k] + d[k][j] ? d[i][k] + d[k][j] : d[i][j];
}


int main(){

    cin >> n >> v >> t;

    fo(MAX)
        for(int j = 0 ; j < MAX ; j ++) d[i][j] = 1e7;

    fo( n ) cin >> node[i];
    fo( v ){
        int a , b , l;
        cin >> a >> b >> l;
        a-- , b--;
        d[a][b] = l + node[b];
        d[b][a] = l + node[a];
    }

    floyd_warshall();

    fo( t ){
        int a , b;
        cin >> a >> b;
        a-- , b--;
        cout << d[a][b] + node[a] << endl;
    }

    return 0;
}