# coding: utf-8 # Your code here! import heapq as hq def dijkstra(edges,start,size): n_node=len(edges) costs=[float("inf") for i in range(n_node)] queue=[[0,start]] while queue: cost,now=hq.heappop(queue) if costs[now]>cost: costs[now]=cost for n_cost,width,nxt in edges[now]: if width>=size: hq.heappush(queue,[cost+n_cost,nxt]) return costs[:] N,M,X=map(int,input().split()) edges=[[] for i in range(N)] for _ in range(M): u,v,a,b=map(int,input().split()) edges[u-1].append([a,b,v-1]) edges[v-1].append([a,b,u-1]) high=10**18+1 low=-1 while high-low>1: middle=(high+low)//2 costs=dijkstra(edges[:],0,middle) if costs[-1]<=X: low=middle else: high=middle print(low)