#include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; template struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; struct UnionFind { explicit UnionFind(const int n) : data(n, -1) {} int root(const int ver) { return data[ver] < 0 ? ver : data[ver] = root(data[ver]); } bool unite(int u, int v) { u = root(u); v = root(v); if (u == v) return false; if (data[u] > data[v]) std::swap(u, v); data[u] += data[v]; data[v] = u; return true; } bool is_same(const int u, const int v) { return root(u) == root(v); } int size(const int ver) { return -data[root(ver)]; } private: std::vector data; }; template struct HeavyLightDecomposition { std::vector parent, subtree, id, inv, head; std::vector cost; explicit HeavyLightDecomposition( const std::vector>>& graph, const int root = 0) : graph(graph) { const int n = graph.size(); parent.assign(n, -1); subtree.assign(n, 1); dfs1(root); id.resize(n); inv.resize(n); head.assign(n, root); int cur_id = 0; dfs2(root, &cur_id); } template void update_v(int u, int v, const Fn f) const { while (true) { if (id[u] > id[v]) std::swap(u, v); f(std::max(id[head[v]], id[u]), id[v] + 1); if (head[u] == head[v]) break; v = parent[head[v]]; } } template T query_v(int u, int v, const F f, const G g, const T id_t) const { T left = id_t, right = id_t; while (true) { if (id_t[u] > id_t[v]) { std::swap(u, v); std::swap(left, right); } left = g(left, f(std::max(id_t[head[v]], id_t[u]), id_t[v] + 1)); if (head[u] == head[v]) break; v = parent[head[v]]; } return g(left, right); } template void update_subtree_v(const int ver, const Fn f) const { f(id[ver], id[ver] + subtree[ver]); } template T query_subtree_v(const int ver, const Fn f) const { return f(id[ver], id[ver] + subtree[ver]); } template void update_e(int u, int v, const Fn f) const { while (true) { if (id[u] > id[v]) std::swap(u, v); if (head[u] == head[v]) { f(id[u], id[v]); break; } else { f(id[head[v]] - 1, id[v]); v = parent[head[v]]; } } } template T query_e(int u, int v, const F f, const G g, const T id_t) const { T left = id_t, right = id_t; while (true) { if (id[u] > id[v]) { std::swap(u, v); std::swap(left, right); } if (head[u] == head[v]) { left = g(left, f(id[u], id[v])); break; } else { left = g(left, f(id[head[v]] - 1, id[v])); v = parent[head[v]]; } } return g(left, right); } template void update_subtree_e(const int ver, const Fn f) const { f(id[ver], id[ver] + subtree[ver] - 1); } template T query_subtree_e(const int ver, const Fn f) const { return f(id[ver], id[ver] + subtree[ver] - 1); } int lowest_common_ancestor(int u, int v) const { while (true) { if (id[u] > id[v]) std::swap(u, v); if (head[u] == head[v]) break; v = parent[head[v]]; } return u; } private: std::vector>> graph; void dfs1(const int ver) { for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) { Edge& e = graph[ver][i]; if (e.dst != parent[ver]) { parent[e.dst] = ver; dfs1(e.dst); subtree[ver] += subtree[e.dst]; if (subtree[e.dst] > subtree[graph[ver].front().dst]) { std::swap(e, graph[ver].front()); } } } } void dfs2(const int ver, int* cur_id) { id[ver] = (*cur_id)++; inv[id[ver]] = ver; for (const Edge& e : graph[ver]) { if (e.dst != parent[ver]) { head[e.dst] = (e.dst == graph[ver].front().dst ? head[ver] : e.dst); cost.emplace_back(e.cost); dfs2(e.dst, cur_id); } } } }; template struct SparseTable { using BinOp = std::function; SparseTable() = default; explicit SparseTable(const std::vector& a, const BinOp bin_op) { init(a, bin_op); } void init(const std::vector& a, const BinOp bin_op_) { bin_op = bin_op_; const int n = a.size(); assert(n > 0); lg.assign(n + 1, 0); for (int i = 2; i <= n; ++i) { lg[i] = lg[i >> 1] + 1; } const int table_h = std::countr_zero(std::bit_floor(a.size())) + 1; data.assign(table_h, std::vector(n)); std::copy(a.begin(), a.end(), data.front().begin()); for (int i = 1; i < table_h; ++i) { for (int j = 0; j + (1 << i) <= n; ++j) { data[i][j] = bin_op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]); } } } Band query(const int left, const int right) const { assert(left < right); const int h = lg[right - left]; return bin_op(data[h][left], data[h][right - (1 << h)]); } private: BinOp bin_op; std::vector lg; std::vector> data; }; int main() { int n, k; ll c; cin >> n >> k >> c; vector u(k), v(k), w(k), p(k); REP(i, k) cin >> u[i] >> v[i] >> w[i] >> p[i], --u[i], --v[i]; vector order(k); iota(order.begin(), order.end(), 0); ranges::sort(order, {}, [&](const int i) -> int { return w[i]; }); vector is_used(k, false); vector>> tree(n); UnionFind union_find(n); ll cost = 0; for (const int i : order) { if (union_find.unite(u[i], v[i])) { is_used[i] = true; tree[u[i]].emplace_back(u[i], v[i], w[i]); tree[v[i]].emplace_back(v[i], u[i], w[i]); cost += w[i]; } } if (cost > c) { cout << "-1\n"; return 0; } const HeavyLightDecomposition hld(tree); const SparseTable table(hld.cost, [](const ll a, const ll b) { return max(a, b); }); int ans = 0; cout << cost << '\n'; REP(i, k) { if (is_used[i] || cost - hld.query_e(u[i], v[i], [&](const int l, const int r) -> ll { return l == r ? LINF : table.query(l, r); }, [](const ll x, const ll y) -> ll { return max(x, y); }, LINF) + w[i] <= c) { chmax(ans, p[i]); } } cout << ans << '\n'; return 0; }