using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ long[] sum = new long[N]; for(int i=0;i Q = new Queue(); Q.Enqueue(root); while(Q.Count>0){ var now = Q.Dequeue(); foreach(var nxt in E[now]){ if(nxt == parent[0][now])continue; sum[nxt] += sum[now]; Q.Enqueue(nxt); } } long ans = 0; int from,to; long w; for(;M>0;M--){ var d = ria(); from = d[0]; to = d[1]; w = (long) d[2]; var p = lca(from,to); long weight = w * (sum[from] + sum[to] - 2*sum[p] + U[p]); ans += weight; } Console.WriteLine(ans); } public Sol(){ N=ri(); E=new List[N]; for(int i=0;i(); for(int i=0;i[] E; int[][] parent; int[] depth; static int lmax=24; int root; int lca(int u,int v){ if(depth[u]>depth[v])return lca(v,u); for(int i=0;i>i)&1) >0 ){ v=parent[i][v]; } } if(u==v)return u; for(int i=lmax-1;i>=0;i--){ if(parent[i][u]!=parent[i][v]){ u=parent[i][u]; v=parent[i][v]; } } return parent[0][u]; } void LCAInit(){ parent=new int[lmax][]; for(int i=0;i Q=new Queue(); parent[0][strt]=-1;depth[strt]=0; Q.Enqueue(strt); while(Q.Count>0){ int now=Q.Dequeue(); int par=parent[0][now]; foreach(int v in E[now]){ if(v!=par){ parent[0][v]=now;depth[v]=depth[now]+1; Q.Enqueue(v); } } } } static String rs(){return Console.ReadLine();} static int ri(){return int.Parse(Console.ReadLine());} static long rl(){return long.Parse(Console.ReadLine());} static double rd(){return double.Parse(Console.ReadLine());} static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);} static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));} static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));} static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));} }