// -*- coding:utf-8-unix -*- // #![feature(map_first_last)] #![allow(dead_code)] #![allow(unused_imports)] #![allow(unused_macros)] // use core::num; use std::cmp::*; use std::fmt::*; use std::hash::*; use std::iter::FromIterator; use std::*; use std::{cmp, collections, fmt, io, iter, ops, str}; const INF: i64 = 1223372036854775807; const UINF: usize = INF as usize; const LINF: i64 = 2147483647; const INF128: i128 = 1223372036854775807000000000000; const MOD1: i64 = 1000000007; const MOD9: i64 = 998244353; const MOD: i64 = MOD9; // const MOD: i64 = MOD2; const UMOD: usize = MOD as usize; const M_PI: f64 = 3.14159265358979323846; // use proconio::input; // const MOD: i64 = INF; use cmp::Ordering::*; use std::collections::*; use std::io::stdin; use std::io::stdout; use std::io::Write; macro_rules! p { ($x:expr) => { //if expr println!("{}", $x); }; } macro_rules! vp { // vector print separate with space ($x:expr) => { println!( "{}", $x.iter() .map(|x| x.to_string()) .collect::>() .join(" ") ); }; } macro_rules! d { ($x:expr) => { eprintln!("{:?}", $x); }; } macro_rules! yn { ($val:expr) => { if $val { println!("Yes"); } else { println!("No"); } }; } macro_rules! map{ // declear btreemap ($($key:expr => $val:expr),*) => { { let mut map = ::std::collections::BTreeMap::new(); $( map.insert($key, $val); )* map } }; } macro_rules! set{ // declear btreemap ($($key:expr),*) => { { let mut set = ::std::collections::BTreeSet::new(); $( set.insert($key); )* set } }; } fn main() { solve(); } // use str::Chars; #[allow(dead_code)] fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[allow(dead_code)] fn read_mat(n: u32) -> Vec> { (0..n).map(|_| read_vec()).collect() } #[allow(dead_code)] fn readii() -> (i64, i64) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } #[allow(dead_code)] fn readiii() -> (i64, i64, i64) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2]) } #[allow(dead_code)] fn readuu() -> (usize, usize) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } #[allow(dead_code)] fn readff() -> (f64, f64) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } fn readcc() -> (char, char) { let mut vec: Vec = read_vec(); (vec[0], vec[1]) } fn readuuu() -> (usize, usize, usize) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2]) } #[allow(dead_code)] fn readiiii() -> (i64, i64, i64, i64) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2], vec[3]) } #[allow(dead_code)] fn readuuuu() -> (usize, usize, usize, usize) { let mut vec: Vec = read_vec(); (vec[0], vec[1], vec[2], vec[3]) } fn read_imat(h: usize) -> Vec> { (0..h).map(|_| read_vec()).collect() } fn read_cmat(h: usize) -> Vec> { (0..h).map(|_| read::().chars().collect()).collect() } pub struct Dsu { n: usize, // root node: -1 * component size // otherwise: parent parent_or_size: Vec, } impl Dsu { // 0 <= size <= 10^8 is constrained. pub fn new(size: usize) -> Self { Self { n: size, parent_or_size: vec![-1; size], } } pub fn merge(&mut self, a: usize, b: usize) -> usize { assert!(a < self.n); assert!(b < self.n); let (mut x, mut y) = (self.leader(a), self.leader(b)); if x == y { return x; } if -self.parent_or_size[x] < -self.parent_or_size[y] { std::mem::swap(&mut x, &mut y); } self.parent_or_size[x] += self.parent_or_size[y]; self.parent_or_size[y] = x as i32; x } pub fn same(&mut self, a: usize, b: usize) -> bool { assert!(a < self.n); assert!(b < self.n); self.leader(a) == self.leader(b) } pub fn leader(&mut self, a: usize) -> usize { assert!(a < self.n); if self.parent_or_size[a] < 0 { return a; } self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32; self.parent_or_size[a] as usize } pub fn size(&mut self, a: usize) -> usize { assert!(a < self.n); let x = self.leader(a); -self.parent_or_size[x] as usize } pub fn groups(&mut self) -> Vec> { let mut leader_buf = vec![0; self.n]; let mut group_size = vec![0; self.n]; for i in 0..self.n { leader_buf[i] = self.leader(i); group_size[leader_buf[i]] += 1; } let mut result = vec![Vec::new(); self.n]; for i in 0..self.n { result[i].reserve(group_size[i]); } for i in 0..self.n { result[leader_buf[i]].push(i); } result .into_iter() .filter(|x| !x.is_empty()) .collect::>>() } } //https://atcoder.jp/contests/abc294/submissions/39892374 // https://ei1333.github.io/luzhiled/snippets/tree/heavy-light-decomposition.html // Verified by: NUPC2017 H // https://atcoder.jp/contests/njpc2017/submissions/23535017 struct HLDecomp { euler: Vec, head: Vec, rev: Vec, par: Vec, } impl HLDecomp { fn dfs_sz(v: usize, p: usize, g: &mut [Vec], sz: &mut [usize], par: &mut [usize]) { par[v] = p; sz[v] = 1; if g[v].get(0) == Some(&p) { let last = g[v].len() - 1; g[v].swap(0, last); } for i in 0..g[v].len() { let to = g[v][i]; if to == p { continue; } Self::dfs_sz(to, v, g, sz, par); sz[v] += sz[to]; if sz[g[v][0]] < sz[to] { g[v].swap(0, i); } } } fn dfs_euler( v: usize, par: usize, g: &[Vec], euler: &mut [usize], count: &mut usize, head: &mut [usize], rev: &mut [usize], ) { euler[v] = *count; *count += 1; rev[euler[v]] = v; for &to in &g[v] { if to == par { continue; } head[to] = if g[v][0] == to { head[v] } else { to }; Self::dfs_euler(to, v, g, euler, count, head, rev); } } pub fn new(g: &[Vec]) -> Self { let mut g = g.to_vec(); let n = g.len(); let mut sz = vec![0; n]; let mut par = vec![0; n]; Self::dfs_sz(0, n, &mut g, &mut sz, &mut par); let mut euler = vec![0; n]; let mut count = 0; let mut head = vec![0; n]; let mut rev = vec![0; n]; Self::dfs_euler(0, n, &g, &mut euler, &mut count, &mut head, &mut rev); HLDecomp { euler: euler, head: head, rev: rev, par: par, } } #[allow(unused)] pub fn get_id(&self, v: usize) -> usize { self.euler[v] } #[allow(unused)] pub fn from_id(&self, id: usize) -> usize { self.rev[id] } // M: commutative // M must not panic. #[allow(unused)] pub fn query T, M: Fn(T, T) -> T>( &self, mut u: usize, mut v: usize, mut f: F, mut m: M, e: T, edge: bool, ) -> T { let mut ans = e; self.divide( u, v, |l, r| { let ptr: *mut T = &mut ans; unsafe { let val = f(l, r); let ans = std::ptr::read(ptr); std::ptr::write(ptr, m(ans, val)) } }, edge, ); ans } pub fn divide(&self, mut u: usize, mut v: usize, mut f: F, edge: bool) { let euler = &self.euler; let head = &self.head; loop { if euler[u] > euler[v] { std::mem::swap(&mut u, &mut v); } if head[u] == head[v] { break; } f(euler[head[v]], euler[v] + 1); v = self.par[head[v]]; } f(euler[u] + if edge { 1 } else { 0 }, euler[v] + 1); } } pub struct SEG { n: usize, buf: Vec, } impl SEG { #[allow(dead_code)] pub fn new(n: usize) -> SEG { SEG { n, buf: vec![M::id(); 2 * n], } } #[allow(dead_code)] pub fn update(&mut self, k: usize, a: M::T) { let mut k = k + self.n; self.buf[k] = a; while k > 0 { k >>= 1; self.buf[k] = M::op(&self.buf[k << 1], &self.buf[(k << 1) | 1]); } } #[allow(dead_code)] pub fn add(&mut self, k: usize, a: &M::T) { let mut k = k + self.n; self.buf[k] = M::op(&self.buf[k], a); while k > 0 { k >>= 1; self.buf[k] = M::op(&self.buf[k << 1], &self.buf[(k << 1) | 1]); } } #[allow(dead_code)] pub fn get(&self, i: usize) -> M::T { self.query(i, i + 1) } #[allow(dead_code)] pub fn query_range>(&self, range: R) -> M::T { let l = match range.start_bound() { std::ops::Bound::Excluded(&x) => { assert!(x > 0); x - 1 } std::ops::Bound::Included(&x) => x, std::ops::Bound::Unbounded => 0, }; let r = match range.end_bound() { std::ops::Bound::Excluded(&x) => x, std::ops::Bound::Included(&x) => (x + 1), std::ops::Bound::Unbounded => self.n, }; self.query(l, r) } #[allow(dead_code)] pub fn query(&self, l: usize, r: usize) -> M::T { let mut vl = M::id(); let mut vr = M::id(); let mut l = l + self.n; let mut r = r + self.n; while l < r { if l & 1 == 1 { vl = M::op(&vl, &self.buf[l]); l += 1; } if r & 1 == 1 { r -= 1; vr = M::op(&self.buf[r], &vr); } l >>= 1; r >>= 1; } M::op(&vl, &vr) } } pub trait Monoid { type T: Clone; fn id() -> Self::T; fn op(a: &Self::T, b: &Self::T) -> Self::T; } pub enum MON {} impl Monoid for MON { type T = usize; fn id() -> Self::T { 0 } fn op(a: &Self::T, b: &Self::T) -> Self::T { max(*a, *b) } } fn solve() { let (n, k, c) = readuuu(); let mut es = vec![]; for i in 0..k { let (u, v, w, p) = readuuuu(); es.push((u - 1, v - 1, w, p)); } let mut uf = Dsu::new(n); let mut mst = vec![]; let mut cost = 0; let mut idx_set = BTreeSet::new(); for i in 0..k { let (u, v, w, p) = es[i]; if !uf.same(u, v) { uf.merge(u, v); mst.push((u, v, w, p)); cost += w; idx_set.insert(i); } } if cost > c { p!(-1); return; } // let n: usize = read(); let mut es2 = vec![]; let mut g = vec![vec![]; n]; // for i in 0..n - 1 { // let (a, b, c) = readuuu(); // es.push((a - 1, b - 1, c)); // g[a - 1].push((b - 1)); // g[b - 1].push((a - 1)); // } for i in 0..mst.len() { let (a, b, c, _) = mst[i]; es2.push((a, b, c)); g[a].push(b); g[b].push(a); } let hld = HLDecomp::new(&g); let mut seg: SEG = SEG::new(n); for i in 0..n - 1 { let (a, b, c) = es2[i]; let ch = if hld.par[a] == b { a } else { b }; let id = hld.get_id(ch); seg.update(id, c); } let mut res = 0; for i in 0..es.len() { let (u, v, w, p) = es[i]; if idx_set.contains(&i) { res = max(res, p); continue; } let cost_ma = hld.query(u, v, |l, r| seg.query_range(l..r), |x, y| x + y, 0, true); if cost - cost_ma + w <= c { res = max(res, p); } } p!(res); return; }