测试数据

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
const int inf=1e9;
int n,m,x,y,z,q;
int fs[10002][10002];
queue<int> tq;
struct edge{
	vector<pair<int,int> > v;
}a[N];
int head[N];
void add(int u,int v,int w){
	a[u].v.push_back({v,w});
	a[v].v.push_back({u,w});
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>x>>y>>z;
		add(x,y,z);
	}
	cin>>q;
	while(q--){
		cin>>x>>y;
		fs[x][x]=fs[y][y]=inf;
		if(fs[x][y]!=0) cout<<fs[x][y]<<endl;
		else{
			tq.push(x);
			while(!tq.empty()){
				int nx=tq.front();tq.pop();
				for(int i=0;i<(int)a[nx].v.size();++i)
					if(fs[x][a[nx].v[i].first]<min(fs[x][nx],a[nx].v[i].second)){ 
						fs[x][a[nx].v[i].first]=min(fs[x][nx],a[nx].v[i].second);
						tq.push(a[nx].v[i].first);
					}	
			}
			if(fs[x][y]==0) cout<<"-1"<<endl;
			else cout<<fs[x][y]<<endl;
		}
	}
	return 0;
}

rt