#include using namespace std; using i64 = int64_t; const i64 INF = LLONG_MAX / 4; void chmin(i64& a, i64 b) { if(a > b) a = b; } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); i64 N, M, X; cin >> N >> M >> X; vector g(N, vector>{}); vector width = {-1}; while(M--) { i64 a, b, d, w; cin >> a >> b >> d >> w; a--; b--; g[a].push_back({b, d, w}); g[b].push_back({a, d, w}); width.push_back(w); } sort(width.begin(), width.end()); auto check = [&](i64 i_) -> bool { const i64 W = width[i_]; vector cost(N, INF); priority_queue q(greater<>{}, vector>{}); auto push = [&](i64 i, i64 c) { if(cost[i] <= c) return; cost[i] = c; q.emplace(c, i); }; push(0, 0); while(q.size()) { auto [c, i] = q.top(); q.pop(); // if(cost[i] != c) continue; for(auto [j, d, w] : g[i]) if(w >= W) push(j, c + d); } return cost.back() <= X; }; i64 ok = 0, ng = width.size(); while(ng - ok > 1) { const i64 mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } cout << width[ok] << endl; }