#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

const int M=4e4+4;

const int maxlog=20;

struct node{

	int id,val;

	node(int id1=0,int val1=0):id(id1),val(val1){}

};

vector<node>e[M];

int deep[M],grand[M][maxlog],dis[M][maxlog],book[M],s,n,root;

void dfs(int x){

	for(int i=1;i<=s;i++){

		grand[x][i]=grand[grand[x][i-1]][i-1];//x的2^i祖先是它2^i-1祖先的2^i-1祖先

		dis[x][i]=dis[x][i-1]+dis[grand[x][i-1]][i-1];//x到它2^i祖先的距离 = x到它2^i-1祖先的距离 + x的2^i-1祖先到它2^i-1祖先距离

		if(!grand[x][i])//到子树跟了

			break;

	}

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

		int v=e[x][i].id;

		if(v!=grand[x][0]){

			grand[v][0]=x;维护父子关系

			deep[v]=deep[x]+1;//维护深度

			dis[v][0]=e[x][i].val;//维护距离

			dfs(v);

		}

	}

}

void init(){

        //n为节点个数

	s=floor(log(n+0.0)/log(2.0));////最多能跳的2^i祖先

	deep[0]=-1;////根结点的祖先不存在，用-1表示

	dfs(root);以root为根节点建树

}

int LCA(int a,int b){

	if(deep[a]>deep[b])//保证a在b上面，便于计算(floor:向下取整；ceil：向上取整）

		swap(a,b);

	int ans=0;

	for(int i=s;i>=0;i--)//类似于二进制拆分，从大到小尝试

		if(deep[a]<deep[b]&&deep[a]<=deep[grand[b][i]])//a在b下面且b向上跳后不会到a上面

			ans+=dis[b][i],b=grand[b][i];//先把深度较大的b往上跳

	for(int i=s;i>=0;i--)

		if(grand[a][i]!=grand[b][i])//a,b的2^i祖先不一样 => 没跳到同样深度位置，接着跳

			ans+=dis[a][i],a=grand[a][i],ans+=dis[b][i],b=grand[b][i];//一起往上跳

	if(a!=b)//没跳到一个地方，那么再往上一个结点就是它们的LCA

		ans+=dis[a][0],ans+=dis[b][0];

	return ans;

}

int main(){

	int t;

	scanf("%d",&t);

	while(t--){

		int m;

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

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

			book[i]=0,e[i].clear(),deep[i]=0;

		memset(grand,0,sizeof(grand));

		memset(dis,0,sizeof(dis));

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

			int x,y,w;

			scanf("%d%d%d",&x,&y,&w);

			book[y]=1;

			e[x].push_back(node(y,w));

			e[y].push_back(node(x,w));

		}

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

			if(!book[i]){

				root=i;

				break;

			}

		}

		init();//cout<<"!!"<<endl;

		while(m--){

			int x,y;

			scanf("%d%d",&x,&y);

			printf("%d\n",LCA(x,y));

		}

	}

	return 0;

}