#include #include #include #include #include using namespace std; using ll = long long; using P = pair; using tu = tuple; int main(void){ ll n, m, x; cin >> n >> m >> x; vector> to(n); for(int i=0; i> u >> v >> a >> b; u--, v--; to[u].emplace_back(v, a, b); swap(u, v); to[u].emplace_back(v, a, b); } auto judge=[&](int tar){ vector dist(n, 1e18); dist[0]=0; priority_queue, greater

> pri; pri.emplace(0, 0); while(pri.size()){ auto [d, id]=pri.top(); pri.pop(); if(dist[id]!=d) continue; for(auto [v, a, b]:to[id]){ if(bnd){ dist[v]=nd; pri.emplace(nd, v); } } } return dist[n-1]<=x; }; int left=-1, right=1e9+1; while(right-left>1){ int mid=(left+right)/2; if(judge(mid)) left=mid; else right=mid; } cout << left << endl; return 0; }