#include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,ll> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 int n, m;

 int num;

 int tot;

 int head[maxn];

 int vis[maxn];

 int ver[*maxn];

 int deep[*maxn];

 int dir[maxn];

 int first[maxn];

 int dp[*maxn][];

 struct node

 {

     int v,w;

     int next;

 }e[*maxn];

 void addEdge(int u, int v, int w)

 {

     e[num].v=v;

     e[num].w=w;

     e[num].next=head[u];

     head[u]=num++;

 }

 void dfs(int u, int dep)

 {

     vis[u]=;

     ver[++tot]=u;   //遍历序列

     first[u]=tot;   //结点第一次出现位置

     deep[tot]=dep;     //深度

     for(int i=head[u];i!=-;i=e[i].next)

     {

         if(!vis[e[i].v])

         {

             int v=e[i].v, w=e[i].w;

             dir[v]=dir[u]+w;   //距离

             dfs(v,dep+);

             ver[++tot]=u;      //回溯

             deep[tot]=dep;

         }

     }

 }

 void ST(int n)

 {

     for(int i=;i<=n;i++)  dp[i][]=i;

     for(int j=;(<<j)<=n;j++)

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

         {

             int a=dp[i][j-],b=dp[i+(<<(j-))][j-];

             dp[i][j]=deep[a]<deep[b]?a:b;

         }

 }

 int RMQ(int L, int R)

 {

     int k=;

     while((<<(k+))<=R-L+)  k++;

     int a=dp[L][k], b=dp[R-(<<k)+][k];

     return deep[a]<deep[b]?a:b;

 }

 int LCA(int u, int v)

 {

     int x=first[u], y=first[v];   //查找出他最先出现的地方

     if(x>y)  swap(x,y);

     int res=RMQ(x,y);    //查询出的是他祖先的下标

     return ver[res];

 }

 int main()

 {

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

     int T;

     scanf("%d",&T);

     while(T--)

     {

         num=; tot=;

         memset(head,-,sizeof(head));

         memset(vis,,sizeof(vis));

         scanf("%d%d",&n,&m);

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

         {

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

             addEdge(u,v,w);

             addEdge(v,u,w);

         }

         dir[]=;

         dfs(,);

         ST(*n-);

         while(m--)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             int lca=LCA(u,v);

             printf("%d\n",dir[u]+dir[v]-*dir[lca]);

         }

     }

     return ;

 }