/*少说话,多做事*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
//#include<bits/stdc++.h>
//ios::sync_with_stdio(0);
//cin.tie(0);
//cout.tie(0);
typedef long long ll;
using namespace std;
/*
第一行:n (n头牛)(1-5e4) Q(询问次数)1-2e5
接下来n行:牛的高度(1-2e5)
接下来Q行 Q次询问
m行(m次询问)i j : 表示i与j之间的距离是多少
DFS+ST:将树看成一个无向图,u和v的公共祖先一定在u和v之间的最短路径上,
(1)DFS:从树T的根开始,进行深度优先遍历(将树看成一个无向图),并记录好每次到达的顶点。
由于每条边恰好经历两次,所以一共记录了2n-1个点,用E[1~2n-1]来表示
(2)计算R:用R[i]表示E数组中第一个值为i的元素下标
如果R[u]<R[v],DFS访问的顺序是E[R[u],R[u]+1,....R[v]].
虽然其中包含u的后代,但深度最小的还是u与v的公共祖先
(3)RMQ:计算RMQ
当R[u]>=R[v]时,LCA[T,u,v]=RMQ(L,R[v],R[u])
否则: LCA[T,u,v]=RMQ(L,R[u],R[v])
*/
const int VMAX = 40010;
const int EMAX = VMAX * 10;
int n, ind;
int net[EMAX], fir[VMAX], w[EMAX], v[EMAX];
int dis[VMAX], vs[VMAX * 5], dep[VMAX * 5], id[VMAX];
bool vis[VMAX];
int dp[VMAX * 5][25];
int k;
void init ()
{
ind = k = 0;
memset(fir, -1, sizeof(fir));
memset(vis, 0, sizeof(vis));
}
void addedge (int f, int t, int val)
{
v[ind] = t;
w[ind] = val;
net[ind] = fir[f];
fir[f] = ind++;
}
void dfs (int x, int d)
{
id[x] = k; //k从0开始 id数组:x的序号是什么
vs[k] = x; //vs数组:第k个是x
dep[k] = d;
k++;
vis[x] = 1; //标记已经遍历过
for (int e = fir[x]; e != -1; e = net[e]) //遍历跟x节点相连的节点
{
int V = v[e];
if (!vis[V])
{
dis[V] = dis[x] + w[e];
dfs(V, d + 1);
vs[k] = x;
dep[k++] = d;
}
}
}
void RMQ_init ()
{
for (int i = 0; i < k; ++i) dp[i][0] = i;
for (int j = 1; (1 << j) <= k; ++j)
{
for (int i = 0; i + (1 << j) - 1 < k; ++i)
{
int a = dp[i][j - 1];
int b = dp[i + (1 << (j - 1))][j - 1];
if (dep[a] > dep[b]) dp[i][j] = b;
else dp[i][j] = a;
}
}
}
int RMQ (int L, int R)
{
int len = 0;
while ((1 << (len + 1)) <= (R - L + 1)) ++len;
int a = dp[L][len];
int b = dp[R - (1 << len) + 1][len];
if (dep[a] > dep[b]) return b;
return a;
}
int LCA (int a, int b)
{
int L = min(id[a], id[b]);
int R = max(id[a], id[b]);
int Min = RMQ(L, R);
return vs[Min];
}
int main ()
{
int T;
scanf("%d", &T);
while (T--)
{
init();
int m;
scanf("%d%d", &n, &m);
for (int i=1;i<n;i++)
{
int a, b, val;
scanf("%d%d%d", &a, &b, &val);
addedge(a, b, val);
addedge(b, a, val); //添加双向边
}
dfs (1, 1); //从根节点开始,遍历
RMQ_init();
while (m--)
{
int a, b;
scanf("%d%d", &a, &b);
int node = LCA(a, b);
printf("%d\n", dis[a] + dis[b] - 2 * dis[node]);
}
}
return 0;
}