劳资没开O2爆挂60分

#define int long long
using namespace std;
int n,m,k;
int d[50010];
int v[50010];
struct aa{
	int v,w;
};
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
vector <aa> a[50010];
bool sou(int zz){
	for (int i = 1 ; i <= n ; i ++){
		d[i] = 1e9;
		v[i] = 0;
	}
	d[1] = 0;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int p = q.top().second;
		q.pop();
		if(v[p])continue;
		v[p]=1;
		for (int i = 0 ; i < a[p].size() ; i ++){
			if(d[a[p][i].v]>d[p]+max(a[p][i].w-zz,(int)0)){
				d[a[p][i].v] = d[p]+max(a[p][i].w-zz,(int)0);
				if(!v[a[p][i].v])q.push(make_pair(d[a[p][i].v],a[p][i].v));
			}
		}
	}
	if(d[n]<=k)return 1;
	else return 0;
}
signed main () {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//	freopen("cs.in","r", stdin);
	cin >> n >> m >> k;
	int l = 0,r = 0;
	for (int i = 1 ; i <= m ; i ++){
		int x,y,v;
		cin >> x >> y >> v;
		r = max(r,v);
		a[x].push_back({y,v});
		a[y].push_back({x,v});
	}
	int ans = 0;
	while(l<=r){
		int mid = (l+r)>>1;
//		cout << l << ' ' << mid << ' ' << r << endl;
		if(sou(mid)){
			r = mid-1;
			ans = mid;
//			cout << "YES";
		}else{
			l = mid+1; 
//			cout << "NO";
		}
//		cout << endl;
	}
	cout << ans;
	return 0;
}
/*
5 6 4
1 2 2
2 3 100
2 4 2
3 4 2
3 5 2
1 5 100
*/