#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef pair P; vector g[100000]; int d[100000]; int p[17][100000]; bool used[100000]; ll ct[100000]; void dfs0(int x){ used[x]=1; for(auto y:g[x]){ if(!used[y]){ d[y]=d[x]+1; ct[y]+=ct[x]; p[0][y]=x; dfs0(y); } } } int lca(int a, int b){ if(d[a]>d[b]) swap(a, b); int a1=a, b1=b; int dd=d[b]-d[a], i=0; while(dd>0){ if(dd%2==1){ b1=p[i][b1]; } dd/=2; i++; } if(a1==b1) return a1; for(int i=16; i>=0; i--){ if(p[i][a1]!=p[i][b1]){ a1=p[i][a1], b1=p[i][b1]; } } return p[0][a1]; } int main() { int n; cin>>n; for(int i=0; i>u>>v; g[u].push_back(v); g[v].push_back(u); } for(int i=0; i>ct[i]; dfs0(0); for(int i=1; i<17; i++){ for(int x=0; x>m; ll ans=0; for(int i=0; i>a>>b>>c; int t=lca(a, b); ll s=ct[b]-ct[t]+ct[a]; if(t>0) s-=ct[p[0][t]]; ans+=(c*s); } cout<