Coco has a tree, whose vertices are conveniently labeled by 1,2,…,n.
There are m chain on the tree, Each chain has a certain weight. Coco would like to pick out some chains any two of which do not share common vertices.
Find out the maximum sum of the weight Coco can pick

The input consists of several test cases. The first line of input gives the number of test cases T (T<=10).
For each tests: 
First line two positive integers n, m.(1<=n,m<=100000)
The following (n - 1) lines contain 2 integers ai bi denoting an edge between vertices ai and bi (1≤ai,bi≤n),
Next m lines each three numbers u, v and val（1≤u，v≤n，0<val<1000）, represent the two end points and the weight of a tree chain.

For each tests:
A single integer, the maximum number of paths.

6

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int N=2e5+;

struct node

{

  int x,y,val;

}line[N];

vector<int>root[N];

inline int R()

{

  char c;int f=;

  for(c=getchar();c<''||c>'';c=getchar());

  for(;c<=''&&c>='';c=getchar())  f=(f<<)+(f<<)+c-'';

  return f;

}

int T,fst[N],go[N],nxt[N],tot,n,m;

int tree[N],g[N][],deep[N],f[N],sum[N],l[N],r[N],cnt;

inline void comb(int a,int b)

{

  nxt[++tot]=fst[a],fst[a]=tot,go[tot]=b;

  nxt[++tot]=fst[b],fst[b]=tot,go[tot]=a;

}

inline void dfs(int u,int fa)

{

  l[u]=++cnt;

  for(int e=fst[u];e;e=nxt[e])

  {

    int v=go[e];if(v==fa)  continue;

    deep[v]=deep[u]+,g[v][]=u;dfs(v,u);

  }

  r[u]=cnt+;

}

inline int get(int a,int b)

{

  int i,j;

  if(deep[a]<deep[b])  swap(a,b);

  for(i=;(<<i)<=deep[a];i++);i--;

  for(j=i;j>=;j--)

    if(deep[a]-(<<j)>=deep[b])  a=g[a][j];

  if(a==b)  return a;

  for(i=;i>=;i--)

    if(g[a][i]!=g[b][i])  a=g[a][i],b=g[b][i];

  return g[a][];

}

inline int query(int pos)

{

  int temp=;

  for(int i=pos;i;i-=(i&(-i)))  temp+=tree[i];

  return temp;

}

inline void insert(int pos,int x)

{

  for(int i=pos;i<=n+;i+=(i&(-i)))  tree[i]+=x;

}

inline void dp(int u,int fa)

{

  sum[u]=,f[u]=;

  for(int e=fst[u];e;e=nxt[e])

  {

    int v=go[e];

    if(v==fa)  continue;

    dp(v,u);sum[u]+=f[v];

  }

  f[u]=sum[u];

  for(int i=;i<root[u].size();i++)

  {

    node temp=line[root[u][i]];

    int a=temp.x,b=temp.y,c=temp.val;

    f[u]=max(f[u],sum[u]+query(l[a])+query(l[b])+c);

  }

  insert(l[u],sum[u]-f[u]);

  insert(r[u],f[u]-sum[u]);

}

inline void pre()

{

  memset(fst,,sizeof(fst));tot=,cnt=;

  memset(g,,sizeof(g));memset(tree,,sizeof(tree));

  for(int i=;i<=n;i++)  root[i].clear();

}

int main()

{

  //freopen("a.in","r",stdin);

  T=R();

  while(T--)

  {

    n=R(),m=R();int a,b,c;

    pre();

    for(int i=;i<n;i++)  a=R(),b=R(),comb(a,b);

    dfs(,);

    for(int i=;i<=;i++)

      for(int j=;j<=n;j++)  g[j][i]=g[g[j][i-]][i-];

    for(int i=;i<=m;i++)

    {

      a=R(),b=R(),c=R();

      int lca=get(a,b);

      root[lca].push_back(i);

      line[i].x=a,line[i].y=b,line[i].val=c;

    }

    dp(,);

    cout<<f[]<<endl;

  }

  return ;

}