There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this
village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.

First line is a single integer T(T<=10), indicating the number of test cases.
  For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road
connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
  Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

2
3 2
1 2 10
3 1 15
1 2
2 3

2 2
1 2 100
1 2
2 1

10
25
100
100
/*
hdu 2586 最近公共祖先LCA
    不懂。。。 
    深搜遍历树，每当回溯到一个节点时，那就已经完成了该节点子树的遍历，
显然这个节点就是子树中点以及其本身的最近公共祖先，以此类推到整个树。
    对于一个点，只有完成了其子树的遍历，我们才改变其父节点的值..
设为 A 和 B，我们搜到A或B时，如果B或A已经被访问过，那么向上回溯，直到第一个父节点已经改变的点，
就是包括点A和点B在内子树的根，这就是我们要找的A和B的最近公共祖先。

*/
#include<iostream>
#include<stdio.h>
using namespace std;

#define N  40001 

struct Edge{  
    int bian,value;  
    int next;  
}edge[2*N]; 


int n,m,e_num,head[N];  
int x[N],y[N],z[N],pre[N],dist[N],vis[N]; 

void AddEdge(int a,int b,int c)//b->a  a->b
{  
    edge[e_num].bian=b; 
    edge[e_num].value=c; 
    edge[e_num].next=head[a];
    head[a]=e_num++; //a之前数量 
    
    edge[e_num].bian=a;
    edge[e_num].value=c; 
    edge[e_num].next=head[b]; 
    head[b]=e_num++;  
} 

int find(int x){  
    if(pre[x]!=x)  
        return pre[x]=find(pre[x]);  
    return pre[x];  
} 

void tarjan(int k)//从1开始 
{  
    int i;  
    vis[k]=1;   
    pre[k]=k; 
     
    for(i=1;i<=m;i++)//m次询问,z[i]保存的是点x[i]和y[i]最近公共祖先
    {  
        if(x[i]==k&&vis[y[i]]) 
            z[i]=find(y[i]);  
        if(y[i]==k&&vis[x[i]]) 
            z[i]=find(x[i]);  
    } 
     
    for(i=head[k];i!=-1;i=edge[i].next)//查找下一个 
    {  
        if(!vis[edge[i].bian])
        {  
            dist[edge[i].bian]=dist[k]+edge[i].value;  
            tarjan(edge[i].bian);  
            pre[edge[i].bian]=k;  
        }  
    }  
}

int main()
{
    int t,a,b,c,i;  
    
//    freopen("test.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        e_num=0;  
        memset(head,-1,sizeof(head));
        
        for(i=1;i<n;i++)
        {  
            scanf("%d%d%d",&a,&b,&c);  
            AddEdge(a,b,c);  
        } 
        
        for(i=1;i<=n;i++) 
            x[i]=y[i]=z[i]=0;  
            
        for(i=1;i<=m;i++)
        {  
            scanf("%d%d",&a,&b);  
            x[i]=a; 
            y[i]=b;  
        } 
        
        memset(vis,0,sizeof(vis));  
        dist[1]=0;  
        tarjan(1);
        
        for(i=1;i<=m;i++)  
            printf("%d\n",dist[x[i]]+dist[y[i]]-2*dist[z[i]]);  
    }
    return 0;
}