[cpp]
#include
#include
#include
#include
using namespace std;
#define MAX 40000
struct edge{
int v,w;
};
vector
vector
bool flag[MAX];
int pre[MAX],father[MAX],path[MAX];
int find(int x){
return x==pre[x] x:pre[x]=find(pre[x]);
}
void LCA(int k)
{
int i,j;
for(i=0;i
int a=mp[k][i].v;
if(!flag[a])
{
flag[a]=1;
path[a]=path[k]+mp[k][i].w;
LCA(a);
pre[a]=k;
for(j=0;j
int b=query[a][j].v;
if(flag[b]&&father[query[a][j].w]==-1)
{
if(a==b) father[query[a][j].w]=0;
else father[query[a][j].w]=path[a]+path[b]-2*path[find(b)];
}
}
}
}
}
int main()
{
int i,j,k,T,n,m,a,b;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
mp[i].clear();
query[i].clear();
flag[i]=0;
father[i]=-1;
pre[i]=i;
path[i]=0;
}
int a,b,c;
edge X;
for(i=1;i
scanf("%d%d%d",&a,&b,&c);
X.v=b;X.w=c;
mp[a].push_back(X);
X.v=a;
mp[b].push_back(X);
}
for(i=1;i<=m;i++)
{ www.2cto.com
scanf("%d%d",&a,&b);
X.v=b;X.w=i;
query[a].push_back(X);
X.v=a;
query[b].push_back(X);
}
flag[1]=1;
// path[1]=0;
LCA(1);
for(i=1;i<=m;i++)
printf("%d\n",father[i]);
}
return 0;
}