Shortest Routes II

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const long long INF = 1e18;

struct Routes{
    int from;
    int to;
    ll weight;
};

int n, m, q;
Routes route[250001];
vector<vector<ll>> dp;

int main(){
    //freopen("routesII.in", "r", stdin);

    cin >> n >> m >> q;
    dp.resize(n+1, vector<ll>(n+1, INF));
    //for(int i=1; i<=n; i++){
        //for(int j=1; j<=n; j++){
            //dp[i][j] = LLONG_MAX;
        //}
    //}
    for(int i=0; i<m; i++){
        cin >> route[i].from >> route[i].to >> route[i].weight;
        //cout << route[i].from << ", " << route[i].to << ", " << route[i].weight << '\n';
        dp[route[i].from][route[i].to] = min(dp[route[i].from][route[i].to], route[i].weight);
        dp[route[i].to][route[i].from] = min(dp[route[i].to][route[i].from], route[i].weight);
    }
    //memset(dp, 1e9, sizeof(dp));
    //dp[1][1] = 1e9;
    for(int i=1; i<=n; i++){
        dp[i][i] = 0;
    }
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
            }
        }
    }
    //for(int i=1; i<=n; i++){
        //for(int j=1; j<=n; j++){
            //cout << dp[i][j] << " ";
        //}
        //cout << '\n';
    //}
    for(int i=0; i<q; i++){
        int a, b;
        cin >> a >> b;
        if(dp[a][b] == INF){
            cout << -1 << '\n';
        }else{
            cout << dp[a][b] << '\n';
        }
    }

    return 0;
}