#include #include using namespace std; using namespace atcoder; // type typedef long long ll; typedef long double ld; using i128 = __int128_t; template using pq = priority_queue; template using pqg = priority_queue, greater>; template using v = vector; #define V vector #define pl pair #define vl v #define vp v #define vm v // IN-OUT #define NYAN ios::sync_with_stdio(false);cin.tie(nullptr);cout< 0; num /= 10) { s.push_back((char)(num % 10) + '0'); } reverse(s.begin(), s.end()); return (os << s); } void Yes(bool b=1) { cout << ( b == 1 ? "Yes" : "No" ) << "\n"; } void YES(bool b=1) { cout << ( b == 1 ? "YES" : "NO" ) << "\n"; } void No(bool b=1) { cout << ( b == 1 ? "No" : "Yes" ) << "\n"; } void NO(bool b=1) { cout << ( b == 1 ? "NO" : "YES" ) << "\n"; } void CIN() {} template void CIN(T &t, U &...u) { cin >> t; CIN(u...); } void COUT() { cout << "\n"; } template void COUT(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; COUT(u...); } #define dump(x) cerr << #x << ":"<< x << "\n"; #define vdump(x) rep(repeat, sz(x)) cerr << repeat << ":" << x[repeat] << "\n"; // macro #define bp __builtin_popcountll #define ALL(x) x.begin(),x.end() #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define reps(i, s, n) for (ll i = s; i < (ll)(n); i++) #define sz(x) (ll)x.size() ll xd[]={0, 1, 0, -1, 1, 1, -1, -1}; ll yd[]={1, 0, -1, 0, 1, -1, -1, 1}; // function templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (bint bl(T x) { int s = 0; while(x) {x >>= 1; s++;} return s; } // bitlength ll rmax(ll a, ll b){return max(a, b);} ll rmin(ll a, ll b){return min(a, b);} ll rsum(ll a, ll b){return a + b;} ll rzero(){return 0;} // constant long double PI = 3.14159265358979; #define INF32 2147483647 #define INF64 9223372036854775807 #define INF 922337203685477580 using mint = modint998244353; // using mint = modint1000000007; /* SOLVE BEGIN ************************************************************************** */ void solve() { ll n, m, x; cin >> n >> m >> x; v>> edge(n); rep(i, m){ ll a, b, c, d; CIN(a, b, c, d); a--; b--; edge[a].emplace_back(b, c, d); edge[b].emplace_back(a, c, d); } auto check = [&](ll wj){ pqg Q; vl dist(n, INF), visit(n); dist[0] = 0; Q.emplace(0, 0); while(sz(Q)){ auto [d, now] = Q.top(); Q.pop(); if(now == n - 1) return true; if(visit[now]) continue; visit[now] = 1; for(auto [next, cost, w] : edge[now]){ if(w < wj) continue; if(dist[now] + cost > x) continue; if(visit[next]) continue; if(chmin(dist[next], dist[now] + cost)) Q.emplace(dist[next], next); } } return false; }; ll ok = -1, ng = INF; while(ng - ok > 1){ ll wj = (ok + ng) / 2; if(check(wj)) ok = wj; else ng = wj; } cout << ok << "\n"; } int main() { NYAN solve(); return 0; }