Problem Description

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.

 

Input

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.

 

Output

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

 

Sample Input

 

Sample Output

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 #define INF 0x3f3f3f3f

 #define LL long long

 const int MAX_N = 4e4+;

 using namespace std;

 struct Edge{int v, nxt, w;}edge[MAX_N<<];              //静态邻接表

 struct Query

 {

     int v, id;

     Query(){};

     Query(int _v, int _id):v(_v), id(_id){};

 };

 vector<Query> q[MAX_N];       // !!!                    //查询关系动态二维矩阵

 int head[MAX_N], cnt;                                   //静态邻接表头节点，边数

 int dis[MAX_N];                                         //各结点到根结点的距离

 int fa[MAX_N];                                          //并查集 祖先数组

 bool vis[MAX_N], in[MAX_N];                             //深搜用，找根结点用

 int ans[MAX_N];                // !!!                   //各查询答案

 int N, M;                                               //结点数，查询数

 void init()

 {

     memset(head, -, sizeof(head));                     //初始化

     memset(vis, false, sizeof(vis));

     memset(in, false, sizeof(in));

     memset(dis, , sizeof(dis));

     memset(ans, , sizeof(ans));

     cnt = ;

 }

 void AddEdge(int from, int to, int weight)              //静态邻接表加边操作

 {

     edge[cnt].v = to;

     edge[cnt].w = weight;

     edge[cnt].nxt = head[from];

     head[from] = cnt++;

 }

 int getfa(int x)                                        //找祖先

 {

     int root = x;

     while(fa[root] != root) root = fa[root];

     int tmp;

     while(fa[x] != root){

         tmp = fa[x];

         fa[x] = root;

         x = tmp;

     }

     return root;

 }

 void dfs(int s)                                         //预处理各根结点到祖先的距离

 {

     int rt = s;

     for(int i = head[s]; i != -; i = edge[i].nxt){

         dis[edge[i].v] = dis[rt] + edge[i].w;

         dfs(edge[i].v);

     }

 }

 void Tarjan(int s)                                      // LCA

 {

     int root = s;

     fa[s] = s;

     for(int i = head[s]; i != -; i = edge[i].nxt){

         int Eiv = edge[i].v;

         Tarjan(Eiv);

         fa[getfa(Eiv)] = s;

     }

     vis[s] = true;

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

         if(vis[q[s][i].v] && !ans[q[s][i].id]){

             ans[q[s][i].id] = dis[q[s][i].v] + dis[s] - *dis[getfa(q[s][i].v)];

         }

     }

 }

 int main()

 {

      int T_case;

      scanf("%d", &T_case);

      while(T_case--){

         init();

         scanf("%d %d", &N, &M);

         for(int i = , u, v, w; i < N; i++){                //建树

             scanf("%d %d %d", &u, &v, &w);

             AddEdge(u, v, w);

             in[v] = true;

         }

         for(int i = , u, v; i <= M; i++){                  //储存查询信息（离线）

             scanf("%d %d", &u, &v);

             q[u].push_back(Query(v, i));

             q[v].push_back(Query(u, i));

         }

         int root = ;

         for(int i = ; i <= N; i++) if(!in[i]){root = i; break;}    //找树根结点

         dfs(root);              //预处理

         Tarjan(root);           //LCA

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

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

         }

         //puts("");

      }

      return ;

 }