#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; 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, vector &rank, vec &v_id, vec &v_len, vec &v_v, vector &G){ rank[v] = rank[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))); v_id[e.to] = i; v_len[e.to] = e.cost; v_v[e.to] = v; dfs(e.to, v, rank, v_id, v_len, v_v, G); } } int find_lca(int x, int y, ll &len, ll &min_cost, vec &id, vector &rank, mat &dbl_v, mat &dbl_len, mat &dbl_id, mat &dbl_min, vector &G){ if(rank[x] > rank[y]) swap(x, y); int d = rank[y] - rank[x], temp_id; Rrep(i, max_log) { if((d>>i)&1) { len += dbl_len[i][y]; 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]){ len += dbl_len[i][x] + dbl_len[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]; } } len += dbl_len[0][x] + dbl_len[0][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; vector G(N, ve(0)); make_G(G); rep(i,N) sort(ALL(G[i])); vector rank(N, -1); mat dbl_min(max_log, vec(N, INF)), dbl_len(max_log, vec(N)), dbl_v(max_log, vec(N)), dbl_id(max_log, vec(N)); rank[N - 1] = 0; dbl_id[0][0] = 0; dbl_len[0][0] = INF; dbl_v[0][0] = dbl_v[0][N - 1] = N - 1; dfs(0, (int)N - 1, rank, dbl_id[0], dbl_len[0], dbl_v[0], G); reps(i, 1, max_log){ rep(v, N){ dbl_len[i][v] = min(dbl_len[i-1][v] + dbl_len[i-1][dbl_v[i-1][v]], INF); 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(0), min_cost(INF); vec id(0); int lca = find_lca(x, y, res, min_cost, id, rank, dbl_v, dbl_len, dbl_id, dbl_min, G); chmin(min_cost, dbl_len[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; } }