#include using namespace std; #define endl '\n' #define ALL(a) (a).begin(),(a).end() #define ALLR(a) (a).rbegin(),(a).rend() #define spa << " " << #define lfs <= (ll)(m); i--) using ll = long long; using ld = long double; const ll MOD = 1e9+7; //const ll MOD = 998244353; const ll INF = 1e18; using P = pair; template void chmin(T &a,T b){if(a>b)a=b;} template void chmax(T &a,T b){if(a void ans(bool x,T1 y,T2 z){if(x)cout< void debug(vector>v,ll h,ll w){for(ll i=0;iv,ll h,ll w){for(ll i=0;i void debug(vectorv,ll n){if(n!=0)cout< vector>vec(ll x, ll y, T w){ vector>v(x,vector(y,w));return v;} ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;} template vectordx={1,0,-1,0,1,1,-1,-1}; vectordy={0,1,0,-1,1,-1,1,-1}; template vector make_v(size_t a,T b){return vector(a,b);} template auto make_v(size_t a,Ts... ts){ return vector(a,make_v(ts...)); } struct edge { ll to,cost; edge(ll x,ll y):to(x),cost(y){}; edge():to(0LL),cost(0LL){}; }; struct LCA{ ll datasize = 21; ll n,root;//rootを根とする頂点数nの根付き木 vectordepth,dist;//0から vector>G; vector>data; LCA(vector>g,ll r):G(g),n(g.size()),root(r){ data.assign(n,vector(datasize,-1)); depth.assign(n,-1LL); dist.assign(n,-1LL); build(); } void build(){ dfs(root,0,0); for(ll i=1;i=0?depth[x]:-1; } ll query(ll x,ll y){ if(depth[x]=1&&depth[y]>=deep(data[x][tmp]))tmp--; x = data[x][tmp]; } tmp = datasize - 1; while(x!=y){ while(tmp>=1&&data[x][tmp]==data[y][tmp])tmp--; x = data[x][tmp]; y = data[y][tmp]; } return x; } }; int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); ll res=0,res1=INF,res2=-INF,buf=0; bool judge = true; ll n;cin>>n; vector>g(n); for(ll i=0;i>u>>v>>c; g[u].emplace_back(v,c); g[v].emplace_back(u,c); } struct LCA lca(g,0); ll q;cin>>q; while(q--){ vectorx(3);cin>>x[0]>>x[1]>>x[2]; ll ret=0; rep(i,0,2)rep(j,i+1,3){ ll r=lca.query(x[i],x[j]); ret+=lca.dist[x[i]]+lca.dist[x[j]]-lca.dist[r]*2; //cout<