How far away？ (HDU

　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.Outputa bland line after each test case.

Sample Input

Sample Output

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<cstdlib>
  7 #include<map>
  8 #include<queue>
  9 #include<vector>
 10 
 11 #define int long long
 12 
 13 using namespace std;
 14 
 15 const int maxx = 1e5 + 5;
 16 
 17 struct node1
 18 {
 19     int u, v, w, next;
 20     node1(){};
 21     node1(int u_, int v_, int w_, int next_)
 22     {
 23         u = u_;
 24         v = v_;
 25         w = w_;
 26         next = next_;
 27     }
 28 } edge[maxx*2];
 29 
 30 struct node2
 31 {
 32     int u, v, id, next;
 33     node2(){};
 34     node2(int u_, int v_, int id_, int next_)
 35     {
 36         u = u_;
 37         v = v_;
 38         id = id_;
 39         next = next_;
 40     }
 41 } qu[maxx*2];
 42 
 43 int cur1, cur2, re[maxx][5];
 44 int head1[maxx], head2[maxx], de[maxx];
 45 int pre[maxx];
 46 bool vis[maxx];
 47 
 48 
 49 void init(int n)
 50 {
 51     cur1 = cur2 = 0;
 52     memset(vis, false, sizeof(vis));
 53     memset(head1, -1, sizeof(head1));
 54     memset(head2, -1, sizeof(head2));
 55     memset(qu, 0, sizeof(qu));
 56     memset(edge, 0, sizeof(edge));
 57     memset(de, 0, sizeof(de));
 58     for(int i=1; i<=n; i++)
 59     {
 60         pre[i] = i;
 61     }
 62 }
 63 
 64 void add_edge(int u, int v, int w)
 65 {
 66     edge[cur1] = (node1){u, v, w, head1[u]};
 67     head1[u] = cur1++;
 68 }
 69 
 70 void add_qu(int u, int v, int id)
 71 {
 72     qu[cur2] = (node2){u, v, id, head2[u]};
 73     head2[u] = cur2++;
 74 }
 75 
 76 int find_pre(int x)
 77 {
 78     if(pre[x]==x) return x;
 79     else return pre[x] = find_pre(pre[x]);
 80 }
 81 
 82 void Tarjan(int x)
 83 {
 84     int pre1, pre2;
 85     vis[x] = true;
 86     for(int i=head1[x]; ~i; i=edge[i].next)
 87     {
 88         int v = edge[i].v;
 89         if(vis[v]==false)
 90         {
 91             de[v] = de[x] + edge[i].w;
 92             Tarjan(v);
 93             pre1 = find_pre(x);
 94             pre2 = find_pre(v);
 95             if(pre1 != pre2)
 96             {
 97                 pre[pre2] = pre1;
 98             }
 99         }
100     }
101 
102     for(int i=head2[x]; ~i; i=qu[i].next)
103     {
104         int v = qu[i].v;
105         if(vis[v]==true)
106         {
107             re[qu[i].id][2] = find_pre(v);
108         }
109     }
110 }
111 
112 signed main()
113 {
114     ios::sync_with_stdio(false);
115     cin.tie(0);
116     cout.tie(0);
117 
118     int t, n, m;
119     int u, v, w;
120 
121     cin >> t;
122     while(t--)
123     {
124         cin >> n >> m;
125         init(n);
126 
127         for(int i=1; i<n; i++)
128         {
129             cin >> u >> v >> w;
130             add_edge(u, v, w);
131             add_edge(v, u, w);
132         }
133         for(int i=1; i<=m; i++)
134         {
135             cin >> u >> v;
136             add_qu(u, v, i);
137             add_qu(v, u, i);
138             re[i][0] = u;
139             re[i][1] = v;
140         }
141 
142         Tarjan(1);
143 
144         for(int i=1; i<=m; i++)
145         {
146             cout << de[re[i][0]] + de[re[i][1]] - 2 * de[re[i][2]] << endl;
147         }
148     }
149 
150     return 0;
151 }