#include //#include //#pragma GCC optimize("Ofast") using namespace std; #define reps(i,s,n) for(int i = s; i < n; i++) #define rep(i,n) reps(i,0,n) #define Rreps(i,n,e) for(int i = n - 1; i >= e; --i) #define Rrep(i,n) Rreps(i,n,0) #define ALL(a) a.begin(), a.end() #define fi first #define se second typedef long long ll; typedef vector vec; typedef vector mat; ll N,M,H,W,Q,K,A,B; string S; typedef pair P; const ll INF = (1LL<<60); template bool chmin(T &a, const T &b){ if(a > b) {a = b; return true;} else return false; } struct edge{ int to; ll cost; edge(){} edge(int a, ll b){ to = a; cost = b; } bool operator < (const edge &e){ return cost < e.cost; } bool operator == (const edge &e){ return cost == e.cost && to == e.to; } }; using ve = vector; const int max_log = 17, max_N = (int)1e+5 + 1; vector G(max_N, ve(0)); vec depth(max_N, -1), len(max_N, 0); mat dbl_min(max_log, vec(max_N, INF)), dbl_v(max_log, vec(max_N)), dbl_id(max_log, vec(max_N)); void make_G(vector &G){ rep(i,N - 2){ int u, v, w; cin>>u>>v>>w; --u; --v; G[u].emplace_back(v, w); G[v].emplace_back(u, w); } G[N - 1].emplace_back(0, INF); } void dfs(int v, int p){ depth[v] = depth[p] + 1; rep(i, (int)G[v].size()) { edge e = G[v][i]; G[e.to].erase(find(ALL(G[e.to]), edge(v, e.cost))); dbl_id[0][e.to] = i; len[e.to] = len[v] + e.cost; dbl_v[0][e.to] = v; dfs(e.to, v); } } int find_lca(int x, int y, ll &min_cost, vec &id){ if(depth[x] > depth[y]) swap(x, y); int d = depth[y] - depth[x], temp_id; Rrep(i, max_log) { if((d>>i)&1) { chmin(min_cost, dbl_min[i][y]); temp_id = dbl_id[i][y]; y = dbl_v[i][y]; auto ite = G[y].begin() + (temp_id == 0); if(ite != G[y].end()) chmin(min_cost, ite->cost); } } if(x == y) { id.push_back(temp_id); return x; } Rrep(i, max_log){ if(dbl_v[i][x] != dbl_v[i][y]){ chmin(min_cost, min(dbl_min[i][x], dbl_min[i][y])); auto ite = G[dbl_v[i][x]].begin() + (dbl_id[i][x] == 0); if(ite != G[dbl_v[i][x]].end()) chmin(min_cost, ite->cost); auto ite2 = G[dbl_v[i][y]].begin() + (dbl_id[i][y] == 0); if(ite2 != G[dbl_v[i][y]].end()) chmin(min_cost, ite2->cost); x = dbl_v[i][x]; y = dbl_v[i][y]; } } id.push_back(dbl_id[0][x]); id.push_back(dbl_id[0][y]); return dbl_v[0][x]; } int main() { cin>>N; ++N; make_G(G); rep(i,N) sort(ALL(G[i])); depth[N - 1] = 0; len[N - 1] = -INF; len[0] = 0; dbl_id[0][0] = 0; dbl_v[0][0] = dbl_v[0][N - 1] = N - 1; dfs(0, (int)N - 1); reps(i, 1, max_log){ rep(v, N){ dbl_v[i][v] = dbl_v[i-1][dbl_v[i-1][v]]; dbl_id[i][v] = dbl_id[i-1][dbl_v[i-1][v]]; auto ite = G[dbl_v[i-1][v]].begin() + (int)(dbl_id[i-1][v] == 0); dbl_min[i][v] = min({dbl_min[i-1][v], dbl_min[i-1][dbl_v[i-1][v]], ite == G[dbl_v[i-1][v]].end() ? INF : ite->cost}); } } cin>>Q; rep(_, Q) { int x, y; cin >> x >> y; --x; --y; ll res, min_cost(INF); vec id(0); int lca = find_lca(x, y, min_cost, id); res = len[x] + len[y] - len[lca] * 2; chmin(min_cost, len[lca] - len[dbl_v[0][lca]]); if (y != lca) swap(x, y); if (!G[x].empty()) chmin(min_cost, G[x][0].cost); if (!G[y].empty() && id.size() == 2) chmin(min_cost, G[y][0].cost); rep(i, (int) G[lca].size()) { if(find(ALL(id), i) == id.end()) { chmin(min_cost, G[lca][i].cost); break; } } cout << (min_cost == INF ? -1 : res + min_cost * 2) << endl; } }