#include #include #include #include #include using namespace std; using ll = long long; int main() { ll N, M, X; cin >> N >> M >> X; ll u, v, a, b; vector>> G(N); for (ll i; i < M; ++i) { cin >> u >> v >> a >> b; --u; --v; G[u].push_back(make_tuple(b, v, a)); G[v].push_back(make_tuple(b, u, a)); } auto f = [&](ll m) { priority_queue> S; vector fixed(N, false); vector D(N, 1e18); D[0] = 0; S.push(make_tuple(0, 0)); while (!S.empty()) { auto [c, i] = S.top(); S.pop(); if (i == N - 1) { break; } if (fixed[i]) { continue; } fixed[i] = true; for (auto& [b, j, a] : G[i]) { if (m > b) { continue; } if (D[j] <= c + a) { continue; } if (c + a > X) { continue; } D[j] = c + a; S.push(make_tuple(c + a, j)); } } return D[N - 1] <= X; }; ll l = -1; ll r = 1e9 + 10; while (r - l > 1) { ll m = (l + r) / 2; if (f(m)) { l = m; } else { r = m; } } cout << l << endl; return 0; }