#include<bits/stdc++.h> using namespace std; #define int long long const int MAXN=100010; int t,n,Q,cnt,lp[MAXN],ans,a[MAXN],p[MAXN]; struct Edge{int v,w,nx;}edge[MAXN<<1];int h[MAXN],CNT;void init(){for(int i=0;i<=n+10;i++)h[i]=-1;CNT=0;} void add_side(int u,int v,int w){edge[++CNT]={v,w,h[u]};h[u]=CNT;edge[++CNT]={u,w,h[v]};h[v]=CNT;} struct side{int u,v,w;}s[MAXN]; bool findloop(int now,int frm,int lst){ // cout<<now<<" "<<frm<<" "<<lst<<":"<<endl; if(now==frm&&lst!=-1){ return 1; } for(int i=h[now];i!=-1;i=edge[i].nx){ // cout<<i<<" "<<edge[i].v<<" "<<now<<" "<<frm<<" "<<lst<<endl; if(((lst&1)?lst+1:lst-1)!=i||lst==-1){ // cout<<114514<<endl; if(findloop(edge[i].v,frm,i)){ lp[++cnt]=edge[i].v; p[cnt]=edge[i].w; // cout<<cnt<<" "<<edge[i].w<<" "<<lp[cnt]<<endl; return 1; } } } return 0; } int dfs(int now,int lst1,int lst2){ int mx=0,nx=0; for(int i=h[now];i!=-1;i=edge[i].nx){ if(edge[i].v!=lst1&&edge[i].v!=lst2){ int tmp=dfs(edge[i].v,now,-1)+edge[i].w; if(tmp<=0)continue; if(tmp>mx){ nx=mx; mx=tmp; } else if(tmp==mx){ nx=tmp; } else if(tmp>nx){ nx=tmp; } } } ans=max(ans,nx+mx); return mx; } int q[MAXN],as[MAXN],hd,ed; void slv(){ans=0; scanf("%lld%lld",&n,&Q); for(int i=1;i<n;i++){ scanf("%lld%lld%lld",&s[i].u,&s[i].v,&s[i].w); } init();for(int i=1;i<n;i++)add_side(s[i].u,s[i].v,s[i].w); ans=max(ans,dfs(1,-1,-1)); int tmps=ans; while(Q--){ init();int u,v,w; scanf("%lld%lld%lld",&u,&v,&w); for(int i=1;i<n;i++)add_side(s[i].u,s[i].v,s[i].w); if(u==v){ printf("%lld\n",tmps); continue; } add_side(u,v,w);cnt=0; bool __=findloop(u,u,-1); ans=tmps;lp[0]=lp[cnt];lp[cnt+1]=lp[1]; for(int i=1;i<=cnt;i++){ a[i]=a[i+cnt]=dfs(lp[i],lp[i-1],lp[i+1]); p[i+cnt]=p[i]; // cout<<lp[i]<<" "<<a[i]<<" "<<p[i]<<endl; } int tmp=0;hd=1,ed=1;as[1]=a[1]; q[ed]=1; //cout<<a[1]<<endl; for(int i=2;i<=2*cnt;i++){ while(hd<=ed&&i-q[hd]>=cnt)hd++; tmp+=p[i-1];as[i]=tmp-a[i]; ans=max(ans,tmp+a[i]-as[q[hd]]); while(hd<=ed&&as[i]<=as[q[ed]]){ ed--; } q[++ed]=i;/* cout<<"ans->"<<tmp+a[i]-as[q[hd]]<<endl; cout<<i<<" "<<lp[i]<<" "<<as[i]<<" "<<tmp<<" "<<hd<<" "<<ed<<":"; for(int j=hd;j<=ed;j++){ cout<<q[j]<<"_"<<as[q[j]]<<" "; } cout<<endl;*/ } for(int i=0;i<=2*n;i++)p[i]=lp[i]=a[i]=0; printf("%lld\n",ans); } } signed main(){ scanf("%lld",&t); while(t--){ slv(); } return 0; }