using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ using(var r = new FastIn(100000)){ N=r.ReadInt(); E=new List[N]; for(int i=0;i(); 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--){ from = r.ReadInt(); to = r.ReadInt(); w = r.ReadLong(); var p = lca(from,to); long weight = w * (sum[from] + sum[to] - 2*sum[p] + U[p]); ans += weight; } Console.WriteLine(ans); } } public Sol(){ } int M; long[] U; int N; List[] 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));} } class FastIn:IDisposable { int Size; byte[] Mem; int ptr; int rsize; bool unfinished; Stream stdin; void Init(int n) { Size = n; Mem = new byte[Size]; rsize=(stdin=Console.OpenStandardInput()).Read(Mem, 0, Size); ptr = 0; unfinished=(rsize == Size); } void Next() { if (unfinished == false) return; rsize=stdin.Read(Mem, 0, Size); ptr = 0; unfinished = (rsize == Size); } ~FastIn(){ stdin.Dispose(); } void IDisposable.Dispose(){ stdin.Dispose(); } public void Dispose(){ stdin.Dispose(); } public FastIn() { Init(100000); } public FastIn(int n) { Init(n); } public int ReadInt() { int ret = 0; int sig = 1; while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) { if(ret==0 && Mem[ptr] == '-'){ sig *= -1; ptr++; continue; } ret = ret * 10 + Mem[ptr++] - '0'; if (ptr == Size) Next(); } while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) { ptr++; if (ptr == Size) Next(); } return ret*sig; } public long ReadLong() { long ret = 0; long sig = 1; while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) { if(ret==0 && Mem[ptr] == '-'){ sig *= -1; ptr++; continue; } ret = ret * 10 + Mem[ptr++] - '0'; if (ptr == Size) Next(); } while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) { ptr++; if (ptr == Size) Next(); } return ret*sig; } public String ReadStr() { //2byte文字はNG StringBuilder sb = new StringBuilder(); while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r') { sb.Append((char)Mem[ptr++]); if (ptr == Size && unfinished) Next(); } while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) { ptr++; if (ptr == Size && unfinished) Next(); } return sb.ToString(); } public String ReadLine() { //極力使わない(split/parseするくらいなら上をつかう) StringBuilder sb = new StringBuilder(); while (ptr < rsize && Mem[ptr] != '\n' && Mem[ptr] != '\r') { sb.Append((char)Mem[ptr++]); if (ptr == Size && unfinished) Next(); } while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r')) { ptr++; if (ptr == Size && unfinished) Next(); } return sb.ToString(); } }