//spfa算法求最短路，邻接表的讲解参考：http://www.cnblogs.com/mengzhong/p/4713421.html
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<cctype> #include<queue> #include<stack> #include<vector> #include<algorithm> using namespace std; typedef long long LL; #define N 100010 #define INF 0x3f3f3f3f int n, m, head[N], k, dist[N], vis[N], used[N]; struct node { int v, len, next; } maps[N]; void add(int u, int v, int len) { maps[k].v=v; maps[k].len=len; maps[k].next=head[u]; head[u]=k++; } int spfa(int a, int b) { memset(vis, 0, sizeof(vis)); memset(used, 0, sizeof(used)); for(int i=0; i<=n; i++) dist[i]=INF; int P; queue<int> q; q.push(a); dist[a]=0; used[a]=1; vis[a]=1; while(q.size()) { P=q.front(); //vis[P]=0; q.pop(); for(int i=head[P]; i!=-1; i=maps[i].next) { int v=maps[i].v; if(dist[v]>maps[i].len+dist[P]) dist[v]=maps[i].len+dist[P]; if(vis[v]) continue; q.push(v); vis[v]=1; used[v]++; if(used[v]>=n) ; } } return dist[b]; } int main() { int T, a, b, c; scanf("%d", &T); while(T--) { k=1; memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); for(int i=0; i<n-1; i++) { scanf("%d%d%d", &a, &b, &c); add(a, b, c); add(b, a, c); } while(m--) { scanf("%d%d", &a, &b); int ans=spfa(a, b); printf("%d ", ans); } } return 0; }