Trem da Mina

#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
#define fi first
#define se second
const int MAX = 10006;
#define OO 0x3f3f3f3f

int n, m;
vector<ii> G[MAX];
bool cor[MAX];
int pai[MAX];
int W[MAX];
int nivel[MAX];
bool mark[MAX];
int F[MAX];
int dist[MAX];
vector<vector<int>> C;
int number[MAX];

void dfs(int v, int p, int d, int e) {
    cor[v] = 1;
    pai[v] = p;
    nivel[v] = d;
    W[v] = e;

    for(int i = 0; i < G[v].size(); i++) {
        int u = G[v][i].fi, w = G[v][i].se;
        if(cor[u] == 0) {
            dfs(u, v, d + 1, w);
        } else if(u != p and !mark[v]) {
            // percorre o ciclo
            int cost = w;
            int a = v, b = u;
            mark[a] = mark[b] = true;
            vector<int> cyc = {a, b};
            while(a != b) {
                if(nivel[a] < nivel[b]) {
                    cost += W[b];
                    b = pai[b];
                    cyc.push_back(b);
                } else {
                    cost += W[a];
                    a = pai[a];
                    cyc.push_back(a);
                }
                mark[a] = mark[b] = true;
            }
            C.push_back(cyc);
            for(int c : cyc) F[c] = cost, number[c] = C.size();
        }
    }
}

void dijkstra(int cycle) {
    memset(dist, 63, sizeof(dist));
    priority_queue<ii> pq;

    for(int i = 0; i < n; i++)
        if(number[i] == cycle)
            pq.push({0, i}), dist[i] = 0;

    while(!pq.empty()) {
        int u = pq.top().second;
        int d = -pq.top().first;
        pq.pop();
        if(d > dist[u]) continue;
        for(int i = 0; i < G[u].size(); i++) {
            int w = G[u][i].first, _d = G[u][i].second;
            if(number[w] == number[u] and number[w] == cycle)
                _d = 0;
            if(dist[w] > d + _d) {
                dist[w] = d + _d;
                pq.push({-dist[w], w});
            }
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w; u--; v--;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    for(int i = 0; i < n; i++)
        if(!cor[i])
            dfs(i, -1, 0, 0);

    int k;
    cin >> k;
    vector<ii> Q;
    for(int i = 0; i < k; i++) {
        int v, T;
        cin >> v >> T; v--;
        Q.push_back({v, T});
    }

    vector<int> ans(k, OO);
    for(int c = 1; c <= C.size(); c++) {
        dijkstra(c);
        for(int i = 0; i < Q.size(); i++)
            if(Q[i].se <= F[C[c - 1].back()])
                ans[i] = min(ans[i], F[C[c - 1].back()] + 2 * dist[ Q[i].fi ]);
    }

    for(int i = 0; i < ans.size(); i++) {
        if(ans[i] >= OO) ans[i] = -1;
        cout << ans[i] << '\n';
    }

    return 0;
}