#include<bits/stdc++.h>
using namespace std;
const int MAXN=40040;
const int MAXM=MAXN*2;
const int INF=0x3f3f3f3f;
struct e{
int u,v,w;
int nxt;
}edge[MAXM];
int head[MAXN],tot;
int N;
void init()
{
tot=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v,int w){
edge[tot].u=u;
edge[tot].v=v;
edge[tot].w=w;
edge[tot].nxt=head[u];
head[u]=tot++;
}
int dep[MAXN],fa[MAXN],cost[MAXN];
int sumcost[MAXN][20],anc[MAXN][20];
bool vis[MAXN];
void bfs(int rt)
{
memset(vis,false,sizeof(vis));
queue<int> q;
q.push(rt);
fa[rt]=-1;
dep[rt]=0;
cost[rt]=0;
vis[rt]=true;
while (!q.empty())
{
int u=q.front();q.pop();
for (int i=head[u];i!=-1;i=edge[i].nxt)
{
int v=edge[i].v;
if (vis[v]) continue;
dep[v]=dep[u]+1;
cost[v]=edge[i].w;
fa[v]=u;
vis[v]=true;
q.push(v);
}
}
}
void preprocess()
{
memset(sumcost,0,sizeof(sumcost));
for (int i=1;i<=N;i++)
{
anc[i][0]=fa[i];
sumcost[i][0]=cost[i];
for (int j=1;(1<<j)<=N;j++) anc[i][j]=-1;
}
for (int j=1;(1<<j)<=N;j++)
{
for (int i=1;i<=N;i++)
if (anc[i][j-1]!=-1)
{
int a=anc[i][j-1];
anc[i][j]=anc[a][j-1];
sumcost[i][j]=sumcost[i][j-1]+sumcost[a][j-1];
}
}
}
int query(int p,int q){
int tmp,log;
if (dep[p]<dep[q]) swap(p,q);
for (log=1;(1<<log)<=dep[p];log++);
log--;
int ans=0;
for (int i=log;i>=0;i--)
{ if (dep[p]-(1<<i)>=dep[q])
{ans+=sumcost[p][i];p=anc[p][i];
}
}
if (p==q) return ans;
for (int i=log;i>=0;i--)
{
if (anc[p][i]!=-1&&anc[p][i]!=anc[q][i])
{
ans+=sumcost[p][i];p=anc[p][i];
ans+=sumcost[q][i];q=anc[q][i];
}
}
ans+=cost[p];ans+=cost[q];
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
init();
int Q;
scanf("%d%d",&N,&Q);
for (int i=0;i<N-1;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
bfs(1);
preprocess();
while (Q--){
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",query(u,v));
}
}
return 0;
}
