#include using namespace std; #define ll long long #define pb push_back #define db double ll n, l; vector adj[200000]; map,ll> mapp; ll timer; vector tin, tout; vector> up; vector> sum; void dfs(ll v, ll p) { tin[v] = ++timer; up[v][0] = p; for (ll i = 1; i <= l; ++i) up[v][i] = up[up[v][i-1]][i-1]; for (ll u : adj[v]) { if (u != p) dfs(u, v); else{ sum[v][0] = mapp[{v,p}]; } } tout[v] = ++timer; } bool is_ancestor(ll u, ll v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } ll lca(ll u, ll v) { if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v; for (ll i = l; i >= 0; --i) { if (!is_ancestor(up[u][i], v)) u = up[u][i]; } return up[u][0]; } void preprocess(ll root) { tin.resize(n); tout.resize(n); timer = 0; l = ceil(log2(n)); up.assign(n, vector(l + 1)); sum.assign(n,vector(l + 1)); dfs(root, root); } ll suma(ll v,ll u) { if(is_ancestor(u,v))return 0; ll temp=0; for(ll i=l;i>=0;i--){ if(u==v)break; if(is_ancestor(v,up[u][i])){ temp+=sum[u][i]; //cout << sum[u][i]<< ' ' << up[u][i]<> n; for(ll i=1;i> x >> y >> val; mapp[{x,y}]=val; mapp[{y,x}]=val; adj[x].pb(y); adj[y].pb(x); } preprocess(0); for(ll i=1;i<=l;++i){ for(ll j=0;j> q; while(q--){ cin >> a >> b >> c; ll poll; if(is_ancestor(lca(a,b),lca(b,c))){ poll=lca(b,c); } else{ poll=lca(a,b); } ll res=0; ll temp=lca(lca(a,b),lca(b,c)); res= suma(temp,a)+suma(temp,b)+suma(temp,c); res-= suma(temp,poll); //if(q==0)suma(lca(c,b),c); cout << poll << ' '<< res << endl; } return 0; }