#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; struct LCA { private: int N,K; vector> G; vector> par; vector depth; int edge_count; void dfs(int u,int p) { par[0][u] = p; if(p != -1) { depth[u] = depth[p] + 1; } for(int v : G[u]) if(v != p) { dfs(v,u); } } public: LCA() {} LCA(int N_) { N = N_; int M = 1; K = 0; while(M < N) { M <<= 1; K++; } if(N == 1) { K++; } par.assign(K,vector(N,-1)); G.resize(N); depth.assign(N,0); edge_count = 0; } void add_edge(int u,int v,bool oriented = false) { assert(0 <= u && u < N && 0 <= v && v < N); G[u].push_back(v); if(!oriented) { G[v].push_back(u); } edge_count++; } void build(int root = 0) { assert(0 <= root && root < N); assert(edge_count == N - 1); dfs(root,-1); for(int k = 1;k < K;k++) { for(int u = 0;u < N;u++) if(par[k - 1][u] != -1) { par[k][u] = par[k - 1][par[k - 1][u]]; } } } int lca(int u,int v) { assert(0 <= u && u < N && 0 <= v && v < N); if(depth[u] < depth[v]) { swap(u,v); } for(int k = 0;k < K;k++) { if((depth[v] - depth[u]) >> k & 1) { u = par[k][u]; } } if(u == v) { return u; } for(int k = K;k--;) { if(par[k][u] == par[k][v]); else { u = par[k][u]; v = par[k][v]; } } assert(par[0][u] == par[0][v]); return par[0][u]; } int get_depth(int u) { assert(0 <= u && u < N); return depth[u]; } int get_log() { return K; } int get_par(int u,int k) { assert(0 <= u && u < N); assert(0 <= k && k < K); return par[k][u]; } }; #include #include #include using namespace std; struct UnionFind { private: int n; vector par,siz; public: UnionFind(int n) :n(n),par(n,-1),siz(n,1) {} int root(int u) { assert(0 <= u && u < n); return (par[u] < 0 ? u:par[u] = root(par[u])); } bool same(int u,int v) { assert(0 <= u && u < n && 0 <= v && v < n); return root(u) == root(v); } bool unite(int u,int v) { assert(0 <= u && u < n && 0 <= v && v < n); u = root(u),v = root(v); if(u == v) return false; if(siz[u] < siz[v]) swap(u,v); siz[u] += siz[v]; par[v] = u; return true; } int size(int u) { assert(0 <= u && u < n); return siz[root(u)]; } vector> components() { vector> ret(n); for(int u = 0;u < n;u++) ret[root(u)].push_back(u); ret.erase(remove_if(ret.begin(),ret.end(),[](vector v) { return v.empty();}),ret.end()); return ret; } }; void Main() { int N,M; long long C; cin >> N >> M >> C; vector> E(M); for(int i = 0;i < M;i++) { int u,v,w,p; cin >> u >> v >> w >> p; u--; v--; E[i] = make_tuple(w,u,v,p); } sort(E.begin(),E.end()); LCA lca(N); vector>> G(N); UnionFind uf(N); vector used(M); int ans = 0; long long cost = 0; for(int i = 0;i < M;i++) { const auto [w,u,v,p] = E[i]; if(uf.unite(u,v)) { cost += w; ans = max(ans,p); lca.add_edge(u,v); G[u].push_back(make_pair(v,w)); G[v].push_back(make_pair(u,w)); used[i] = 1; } } if(cost > C) { cout << "-1\n"; return; } lca.build(); int K = lca.get_log(); vector> dp(K,vector(N,-(int)1e9)); auto dfs = [&](auto dfs,int u,int p,int pw) -> void { if(p != -1) { dp[0][u] = pw; } for(const auto &[v,w] : G[u]) { if(v == p) { continue; } dfs(dfs,v,u,w); } }; dfs(dfs,0,-1,0); for(int k = 1;k < K;k++) { for(int u = 0;u < N;u++) { int p = lca.get_par(u,k - 1); if(p == -1) { continue; } dp[k][u] = max(dp[k - 1][u],dp[k - 1][p]); } } for(int i = 0;i < M;i++) { if(used[i]) { continue; } const auto &[w,u,v,p] = E[i]; if(p <= ans) { continue; } int x = lca.lca(u,v); int mx = 0; { int d = lca.get_depth(u) - lca.get_depth(x); int cur = u; for(int k = 0;k < K;k++) { if(d >> k & 1) { mx = max(mx,dp[cur][k]); cur = lca.get_par(cur,k); } } assert(cur == x); } { int d = lca.get_depth(v) - lca.get_depth(x); int cur = v; for(int k = 0;k < K;k++) { if(d >> k & 1) { mx = max(mx,dp[cur][k]); cur = lca.get_par(cur,k); } } assert(cur == x); } if(cost - mx + w <= C) { ans = max(ans,p); } } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; /* cin >> tt; */ while(tt--) Main(); }