#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=4e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,dep[maxn],W[maxn],fa[maxn],cnt; int son[maxn],siz[maxn],top[maxn],dfn[maxn],idfn[maxn]; vector<pi>E[maxn]; ll ans; struct nd { ll s,pre,suf,ans; bool tg; }; nd operator+(nd a,nd b){ if(!a.tg)return b; if(!b.tg)return a; nd c; c.s=a.s+b.s; c.pre=max(a.pre,b.pre+a.s); c.suf=max(a.suf+b.s,b.suf); c.ans=max({a.ans+b.s,b.ans+a.s,a.pre+b.suf}); c.tg=1; return c; } nd f[maxn],g[maxn]; ll s[maxn]; nd a[maxn],b[maxn]; struct SegTree { struct node { nd f,g; }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void pu(int p){d[p].g=d[ls(p)].g+d[rs(p)].g,d[p].f=d[rs(p)].f+d[ls(p)].f;} void bd(int l,int r,int p){ if(l==r)return d[p].f=a[idfn[l]],d[p].g=b[idfn[l]],void(); int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(p); } nd askf(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return d[p].f; int mid=s+t>>1; if(r<=mid)return askf(l,r,s,mid,ls(p)); if(l>mid)return askf(l,r,mid+1,t,rs(p)); return askf(l,r,mid+1,t,rs(p))+askf(l,r,s,mid,ls(p)); } nd askg(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return d[p].g; int mid=s+t>>1; if(r<=mid)return askg(l,r,s,mid,ls(p)); if(l>mid)return askg(l,r,mid+1,t,rs(p)); return askg(l,r,s,mid,ls(p))+askg(l,r,mid+1,t,rs(p)); } }T; struct info { ll fi,se,th; void add(ll k){ if(k>=fi)th=se,se=fi,fi=k; else if(k>=se)th=se,se=k; else th=max(th,k); } ll ban(ll k){ if(k==fi)return se; return fi; } ll ban(ll x,ll y){ if(x<y)swap(x,y); if(x==fi)return y==se?th:se; return fi; } }d[maxn]; void dfs(int u,int fa){ ::fa[u]=fa;dep[u]=dep[fa]+1,siz[u]=1; d[u]={0,0,0}; for(auto it:E[u]){ int x=it.p1,w=it.p2; if(x!=fa){ W[x]=w,dfs(x,u),d[u].add(d[x].fi+w); if(siz[son[u]]<siz[x])son[u]=x; siz[u]+=siz[x]; } } ans=max(ans,d[u].fi+d[u].se); } void dfs2(int u,int fa){ for(auto it:E[u]){ int x=it.p1,w=it.p2; if(x!=fa){ s[x]=max(s[x],max(s[u],d[u].ban(d[x].fi+w))+w); dfs2(x,u); } } } const ll inf=-1e18; void dfs3(int u,int tp){ ll k=d[u].ban(d[son[u]].fi+W[son[u]]); a[u]={W[u],k,k+W[u],inf,1}; b[u]={W[son[u]],k,k+W[son[u]],inf,1}; if(u!=tp)f[u]=a[u]+f[fa[u]],g[u]=g[fa[u]]+b[u]; else f[u]=a[u],g[u]=b[u]; idfn[dfn[u]=++cnt]=u,top[u]=tp; if(!son[u])return; dfs3(son[u],tp); for(auto x:E[u])if(x.p1!=fa[u]&&x.p1!=son[u])dfs3(x.p1,x.p1); } nd askf(int u,int v,int lst){ nd ans;ans.tg=0; while(top[u]!=top[v]){ int p=top[u]; ll k=d[u].ban(d[lst].fi+W[lst]); ans=ans+(nd){W[u],k,k+W[u],inf,1}; if(u!=p)ans=ans+f[fa[u]]; lst=top[u],u=fa[p]; } if(u!=v){ ll k=d[u].ban(d[lst].fi+W[lst]); ans=ans+(nd){W[u],k,k+W[u],inf,1};u=fa[u]; if(u!=v)ans=ans+T.askf(dfn[v]+1,dfn[u],1,n,1); } return ans; } nd askg(int u,int v,int lst){ nd ans;ans.tg=0; while(top[u]!=top[v]){ int p=top[u]; ll k=d[u].ban(d[lst].fi+W[lst]); ans=(nd){W[lst],k,k+W[lst],inf,1}+ans; if(u!=p)ans=g[fa[u]]+ans; lst=top[u],u=fa[p]; } if(u!=v){ ll k=d[u].ban(d[lst].fi+W[lst]); ans=(nd){W[lst],k,k+W[lst],inf,1}+ans;u=fa[u]; if(u!=v)ans=T.askg(dfn[v]+1,dfn[u],1,n,1)+ans; } return ans; } int lca(int u,int v){ while(top[u]!=top[v]){ if(dep[top[u]]>=dep[top[v]])u=fa[top[u]]; else v=fa[top[v]]; } return dep[u]<dep[v]?u:v; } int kfa(int u,int k){ //cout<<"? "<<u<<" "<<k<<" "<<dep[u]-dep[top[u]]<<" "<<dfn[u]<<endl; while(1){ if(dep[u]-dep[top[u]]>=k)return idfn[dfn[u]-k]; k-=dep[u]-dep[top[u]]+1,u=fa[top[u]]; } return 0; } nd ask(int u,int v){ int p=lca(u,v); if(v==p)swap(u,v); int id=kfa(v,dep[v]-dep[p]-1); //cout<<"! "<<id<<endl; nd ans;ans.tg=0; if(u!=p){ int q=kfa(u,dep[u]-dep[p]-1); ans=(nd){W[u],d[u].fi,d[u].fi+W[u],inf,1}+askf(fa[u],p,u); ll k=d[p].ban(d[id].fi+W[id],d[q].fi+W[q]); k=max(k,s[p]); ans=ans+(nd){W[id],k,k+W[id],inf,1}; }else { ll k=d[p].ban(d[id].fi+W[id]);k=max(k,s[u]); ans=ans+(nd){W[id],k,k+W[id],inf,1}; } ans=ans+askg(fa[v],p,v); //cout<<"!!! "<<ans.ans<<endl; ans=ans+(nd){0,d[v].fi,d[v].fi,inf,1}; return ans; } ll ask(int u,int v,ll w){ if(u==v)return ans; return max(ans,ask(u,v).ans+w); } void slv(){ n=read();int q=read(); up(i,1,n)E[i].clear(),son[i]=fa[i]=dep[i]=s[i]=0;cnt=0; up(i,1,n-1){ int x=read(),y=read(),w=read(); E[x].p_b(m_p(y,w)),E[y].p_b(m_p(x,w)); } ans=0,dfs(1,0);dfs2(1,0);dfs3(1,1); T.bd(1,n,1); while(q--){ int u=read(),v=read();ll w=read(); printf("%lld\n",ask(u,v,w)); } } int main(){ //freopen("c.in","r",stdin),freopen("c.out","w",stdout); int t=read();while(t--)slv(); fclose(stdin),fclose(stdout); return 0; }