题意：一个村子有n个房子，他们用n-1条路连接起来，每两个房子之间的距离为w。有m次询问，每次询问房子a,b之间的距离是多少。

分析：近期公共祖先问题，建一棵树，求出每一点i到树根的距离d[i],每次询问a。b之间的距离=d[a]+d[b]-2*d[LCA(a,b)];LCA(a,b)是a，b的近期公共祖先。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<vector>

using namespace std;

#define N 50005

vector<int> map[N],w[N],query[N],num[N];

int p[N],d[N],res[N];

bool vis[N];

int n;

void Init()

{

	int i;

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

	{

		map[i].clear();

		w[i].clear();

		query[i].clear();

		num[i].clear();

		p[i]=i;

		d[i]=0;

		vis[i]=false;

	}

}

int Find(int x)

{

	if(p[x]!=x)

		p[x]=Find(p[x]);

	return p[x];

}

void Union(int x,int y)

{

	x=Find(x);

	y=Find(y);

	if(x!=y)

		p[y]=x;

}

void Tarjan(int cur,int v)

{

	int size,i,tmp;

	vis[cur]=true;

	d[cur]=v;

	size=map[cur].size();

	for(i=0;i<size;i++)

	{

		tmp=map[cur][i];

		if(vis[tmp]) continue;

		Tarjan(tmp,v+w[cur][i]);

		Union(cur,tmp);

	}

	size=query[cur].size();

	for(i=0;i<size;i++)

	{

		tmp=query[cur][i];

		if(!vis[tmp])continue;

		res[num[cur][i]]=d[cur]+d[tmp]-2*d[Find(tmp)];

	}

}

int main()

{

	int T,q,a,b,c,i;

	scanf("%d",&T);

	while(T--)

	{

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

		Init();

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

		{

			scanf("%d%d%d",&a,&b,&c);

			map[a].push_back(b);

			w[a].push_back(c);

			map[b].push_back(a);

			w[b].push_back(c);

		}

		for(i=0;i<q;i++)

		{

			scanf("%d%d",&a,&b);

			query[a].push_back(b);

			query[b].push_back(a);

			num[a].push_back(i);

			num[b].push_back(i);

		}

		Tarjan(1,0);

		for(i=0;i<q;i++)

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

	}

	return 0;

}