#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 using namespace std;

 const int maxn = ;

 struct node{//询问的结点x,y

     int x,y;

     int lca;

 }query[maxn];

 struct e{//建边

     int to;

     int val;

 };

 int dis[maxn];

 vector<e> G[maxn];

 vector<int> Q[maxn];

 bool vis[maxn];

 int N;

 int fa[maxn];

 void init(){//初始化父亲结点

     for(int i = ;i<maxn;i++) fa[i] = i;

 }

 int find(int x){//并查集find函数

     if(x == fa[x]) return x;

     return fa[x] = find(fa[x]);

 }

 void tarjan(int cur){

     vis[cur] = true;//标记cur已访问过

     for(auto q:Q[cur]){//遍历包含cur结点的询问

         if(query[q].x == cur){

             if(vis[query[q].y]) {//若x == cur且y已经被访问过,搜y的祖先，就是其LCA

                 query[q].lca = find(query[q].y);

             }

         }

         else{

             if(vis[query[q].x]){//若y == cur且x已经被访问过,搜x的祖先，就是其LCA

                 query[q].lca = find(query[q].x);

             }

         }

     }

     for(auto e:G[cur]){//遍历cur结点的儿子结点

         int v = e.to , len = e.val ;

         if(vis[v]) continue;

         dis[v] = dis[cur] + len;//dis记录cur到root的距离

         tarjan(v);

         fa[v] = cur; //设置cur结点子节点的父亲为cur

     }

 }

 int main(){

     int t;scanf("%d",&t);

     while(t--){

         scanf("%d",&N);

         int q;

         memset(vis,,sizeof(vis));

         init();

         for(int i = ;i<maxn;i++) {//初始化

             Q[i].clear() ,G[i].clear() ;

             query[i].lca = ,query[i].x = ,query[i].y = ;

         }

         scanf("%d",&q);

         for(int i = ;i<=N-;i++){

             int u,v,k;

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

             G[u].push_back({v,k}); //建图

             G[v].push_back({u,k});

         }

         for(int i = ;i<=q;i++){

             scanf("%d%d",&query[i].x ,&query[i].y );

             Q[query[i].x ].push_back(i);

             Q[query[i].y ].push_back(i);  //离线存储所有询问 ，i为标号

         }

         tarjan();

         for(int i = ;i<=q;i++){

             int LCA = query[i].lca ;

             int ans = dis[query[i].x ] + dis[query[i].y ] - *dis[LCA];//输出所有的询问

             printf("%d\n",ans);

         }

     }

     return ;

 }