#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount #define popcountll __builtin_popcountll using namespace std; typedef long long int ll; typedef pair P; template struct SegmentTree{ using F=function; int sz; vector seg; const F f; const Monoid e; SegmentTree(int n, const F f, const Monoid &e): f(f), e(e){ sz=1; while(sz v): f(f), e(e){ sz=1; while(sz=1; i--){ seg[i]=f(seg[2*i], seg[2*i+1]); } } void update(int k, const Monoid &x){ k+=sz; seg[k]=x; while(k>1){ k>>=1; seg[k]=f(seg[2*k], seg[2*k+1]); } } Monoid query(int a, int b){ a+=sz, b+=sz; Monoid retl=e, retr=e; for(;a>=1, b>>=1){ if(b&1) retr=f(seg[--b], retr); if(a&1) retl=f(retl, seg[a++]); } return f(retl, retr); } Monoid operator[](const int &k) const{ return seg[k+sz]; } }; struct HeavyLightDecomposition{ vector> g; vector in, out, rev, cnt, head, par; HeavyLightDecomposition(const vector> &g):g(g), in(g.size()), out(g.size()), rev(g.size()), cnt(g.size()), head(g.size()), par(g.size()){} void dfs(int x, int p){ cnt[x]=1, par[x]=p; int mx=-1, k=-1; for(int i=0; i0) swap(g[x][k], g[x][0]); } void dfs2(int x, int p, int &t){ in[x]=t++; rev[in[x]]=x; for(int i=0; i=in[u]) return rev[in[v]-k]; k-=in[v]-in[u]+1; v=par[u]; } } int lca(int u, int v){ for(; ; v=par[head[v]]){ if(in[u]>in[v]) swap(u, v); if(head[u]==head[v]) return u; } } template T query(int u, int v, const F &f, const T &e, const Q &q){ T ret=e; for(; ; v=par[head[v]]){ if(in[u]>in[v]) swap(u, v); if(head[u]==head[v]) break; ret=f(q(in[head[v]], in[v]+1), ret); } ret=f(q(in[u], in[v]+1), ret); return ret; } }; template struct SparseTable{ using F=function; const F f; const T e; vector> spt; vector vlog; SparseTable(const F f, const T &e, const vector &v):f(f), e(e){ int b=0, n=v.size(); while((1<(n)); for(int i=0; i>1]+1; } T query(int l, int r){ int b=vlog[r-l]; return f(spt[b][l], spt[b][r-(1<>n; vector> g(n); vector> to(n); for(int i=0; i>u>>v>>w; u--; v--; g[u].push_back(v); g[v].push_back(u); to[u].push_back(w); to[v].push_back(w); } int n1=n; for(int i=1; ib.first) swap(a, b); return P(a.first, min(b.first, a.second)); }; HeavyLightDecomposition hld(g); hld.build(); ll s[200020], wp[200020]; int d[200020]; int par[200020]; par[0]=-1, s[0]=0, d[0]=0, wp[0]=INF; auto dfs=[&](auto dfs, int x, int p)->void{ for(int i=0; i v(n1); for(int i=0; i seg(minp, P(INF, INF), v); //SegmentTree

seg(n1, minp, P(INF, INF), v); auto qr=[&](int l, int r){ return seg.query(l, r);}; auto solve1=[&](int x, int p, int p1){ int x1=g[x].back(); ll w1=to[x].back(); if(x1==par[x]){ x1=g[x][0]; w1=to[x][0]; } return minp(hld.query(x1, p1, minp, P(INF, INF), qr), P(w1, INF)); }; auto solve=[&](int x, int y){ int p=hld.lca(x, y); if(p==x){ int p1=hld.la(y, d[y]-d[p]-1); ll myon=min(solve1(y, p, p1).first, wp[p]); if(myon==INF) return -1ll; else return s[y]-s[p]+2*myon; }else if(p==y){ int p1=hld.la(x, d[x]-d[p]-1); ll myon=min(solve1(x, p, p1).first, wp[p]); if(myon==INF) return -1ll; else return s[x]-s[p]+2*myon; } int p1=hld.la(x, d[x]-d[p]-1), p2=hld.la(y, d[y]-d[p]-1); P mn1=solve1(x, p, p1), mn2=solve1(y, p, p2); ll mn0=mn1.first; if(mn1.first==wp[p2]) mn0=mn1.second; if(mn2.first==wp[p1]) mn0=min(mn0, mn2.second); else mn0=min(mn0, mn2.first); mn0=min(mn0, wp[p]); if(mn0==INF) return -1ll; else return s[x]+s[y]-2*s[p]+2*mn0; }; int q; cin>>q; while(q--){ int x, y; cin>>x>>y; x--; y--; printf("%lld\n", solve(x, y)); } return 0; }