//A-HDU2586-LCA-tarjan离线版

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<bitset>

 #include<cassert>

 #include<cctype>

 #include<cmath>

 #include<cstdlib>

 #include<ctime>

 #include<deque>

 #include<iomanip>

 #include<list>

 #include<map>

 #include<queue>

 #include<set>

 #include<stack>

 #include<vector>

 using namespace std;

 typedef long long ll;

 const double PI=acos(-1.0);

 const double eps=1e-;

 const ll mod=1e9+;

 const int inf=0x3f3f3f3f;

 const int maxn=4e4+;

 const int maxm=+;

 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

 struct node{

     int x,y;

     //node(int xx,int yy){

     //    x=xx,y=yy;

     //}node(){}

 };

 vector<node> edge[maxn],q[maxn];

 int ans[maxn],dis[maxn],fa[maxn],vis[maxn];

 int n,m,aa,bb,cc;

 int find(int x)//找父节点(祖先)

 {

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

 }

 void unio(int x,int y)//并查集压缩路径

 {

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

 }

 void init()//初始化

 {

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

         edge[i].clear();

         q[i].clear();

         fa[i]=i;//初始化自己的父亲节点是自己

         vis[i]=;

         ans[i]=;

         dis[i]=;

     }

 }

 void dfs(int x)//tarjan

 {

     vis[x]=;

     for(int i=;i<edge[x].size();i++){

         int v=edge[x][i].x;

         if(!vis[v]){

             dis[v]=dis[x]+edge[x][i].y;

             dfs(v);

             unio(x,v);

         }

     }

     for(int i=;i<q[x].size();i++){

         int v=q[x][i].x;

         if(vis[v])

             ans[q[x][i].y]=dis[x]+dis[v]-*dis[find(v)];

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--){

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

         init();

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

             scanf("%d%d%d",&aa,&bb,&cc);

             //edge[aa].push_back(node(bb,cc));

             //edge[bb].push_back(node(aa,cc));

             edge[aa].push_back({bb,cc});

             edge[bb].push_back({aa,cc});

         }

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

             scanf("%d%d",&aa,&bb);

             //q[aa].push_back(node(bb,i));

             //q[bb].push_back(node(aa,i));

             q[aa].push_back({bb,i});

             q[bb].push_back({aa,i});

         }

         dfs();

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

         printf("%d\n",ans[i]);

     }

 }