1 #include<iostream>

 2 #include<algorithm>

 3 using namespace std;

 4 const int maxn=40005;

 5 int n,m;

 6 int head[maxn],to[maxn<<1],w[maxn<<1],nxt[maxn<<1],tot;

 7 int fa[maxn],dep[maxn],son[maxn],top[maxn],size[maxn],dis[maxn];

 8

 9 void add(int x,int y,int z){

10     nxt[++tot]=head[x];

11     head[x]=tot;

12     to[tot]=y;

13     w[tot]=z;

14 }

15

16 void dfs1(int u,int f){

17     fa[u]=f,size[u]=1,dep[u]=dep[f]+1;

18     for(int i=head[u];i;i=nxt[i]){

19         int v=to[i];

20         if(v==f) continue;

21         dis[v]=dis[u]+w[i];

22         dfs1(v,u);

23         size[u]+=size[v];

24         if(size[v]>size[son[u]]) son[u]=v;

25     }

26 }

27

28 void dfs2(int u){

29     if(u==son[fa[u]]) top[u]=top[fa[u]];

30     else top[u]=u;//求top数组

31     for(int i=head[u];i;i=nxt[i]){

32         int v=to[i];

33         if(v!=fa[u]) dfs2(v);

34     }

35 }

36

37 int LCA(int u,int v){

38     while(top[u]!=top[v]){

39         if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];

40         else v=fa[top[v]];

41     }

42     return dep[u]>dep[v]?v:u;

43 }

44

45 int main(){

46     int T;

47     scanf("%d",&T);

48     while(T--){

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

50         for(int i=1;i<=n;i++) head[i]=dep[i]=dis[i]=son[i]=0;

51         tot=0;

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

53             int x,y,z;

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

55             add(x,y,z);add(y,x,z);

56         }

57         dfs1(1,0);

58         dfs2(1);

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

60             int x,y;

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

62             int k=LCA(x,y);

63             printf("%d\n",dis[x]+dis[y]-2*dis[k]);

64         }

65     }

66     return 0;

67 }