RT.p4880

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct d{
	int v,w;
};
struct xc{
	int num;
	int ds;
};
struct xp{
	int time;
	int dip;
};
vector<d>a[100005];
xc dis[100005];
xp lis[100005];
queue<int>q;
int n,m,b,e;
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>b>>e;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		a[u].push_back({v,w});
		a[v].push_back({u,w});
	}
	memset(dis,0x3f3f,sizeof(dis));
	dis[b].ds=0;
	q.push(b);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(auto ed:a[u]){
			int v=ed.v,w=ed.w;
			if(dis[v].ds>dis[u].ds+w){
				dis[v].ds=dis[u].ds+w;
				q.push(v);
			}
		}
	}
	for(int i=1;i<=n;i++)
		dis[i].num=i;
	
	int t,ans=LLONG_MAX;
	cin>>t;
	for(int i=1;i<=t;i++){
		int ai,x;
		cin>>ai>>x;
		lis[i].time=ai;
		lis[i].dip=x;
		if(dis[x].ds<=ai)ans=min(ans,ai);
	}
	if(ans==LLONG_MAX){
	cout<<dis[lis[t].dip].ds;
	exit(0);
}
	cout<<ans;
	return 0;
}``````