class UF: def __init__(self,n): self.p = [-1]*n def f(self,x): if self.p[x]<0: return x else: self.p[x] = self.f(self.p[x]); return self.p[x] def u(self,x,y): x = self.f(x); y = self.f(y) if x==y: return if -self.p[x]<-self.p[y]: x,y = y,x self.p[x] += self.p[y]; self.p[y] = x def s(self,x,y): return self.f(x) == self.f(y) class DoublingLCA: def __init__(self,n,adj,root=0): self.ancestor,self.depth,self.weight = [[-1]*(n+1)],[-1]*n,[[0]*(n+1)] stack = [(root,-1,0)] while stack: v,p,dep = stack.pop() self.ancestor[0][v],self.depth[v] = p,dep for c,w in adj[v]: if c!=p: stack.append((c,v,dep+1)) self.weight[0][c] = max(self.weight[0][c],w) for _ in range(max(self.depth).bit_length()-1): next_ancestor = []; next_weight = [] for v in self.ancestor[-1]: u = self.ancestor[-1][v] next_ancestor.append(u) next_weight.append(max(self.weight[-1][u],self.weight[-1][v])) self.ancestor.append(next_ancestor) self.weight.append(next_weight) def get_kth_ancestor(self,v,k): w = 0 for i in range(k.bit_length()): if k>>i&1: v = self.ancestor[i][v] w = max(w,self.weight[i][v]) return v,w def get_max_weight(self,u,v): depu,depv = self.depth[u],self.depth[v] if depu>depv: u,v,depu,depv = v,u,depv,depu v,w = self.get_kth_ancestor(v,depv-depu) if u==v: return w for k in range(depu.bit_length()-1,-1,-1): nu,nv = self.ancestor[k][u],self.ancestor[k][v] w = max(w,self.weight[k][u],self.weight[k][v]) if nu!=nv: u,v = nu,nv return w n,k,c = map(int,input().split()) wpuv = [] for _ in range(k): u,v,w,p = map(int,input().split()) wpuv.append((w,p,u-1,v-1)) uf = UF(n); d = m = 0; adj = [[] for _ in range(n)] for w,p,u,v in sorted(wpuv): if uf.s(u,v): continue uf.u(u,v); d += w; m = max(m,p) adj[u-1].append((v,w)); adj[v-1].append((u,w)) if d>c: exit(print(-1)) lca = DoublingLCA(n,adj) for w,p,u,v in wpuv: if d-lca.get_max_weight(u,v)+w<=c: m = max(m,p) print(m)