def main(): from sys import stdin, setrecursionlimit input = stdin.readline readline = stdin.readline import heapq def dijkstra(s,p): hq=[(0,s,0)] ans=[] heapq.heapify(hq) # リストを優先度付きキューに変換 cost=[10**18+1]*N # 行ったことのないところはinf cost[s]=0 # 開始地点は0 while hq: c,v,pre=heapq.heappop(hq) if c>cost[v]: # コストが現在のコストよりも高ければスルー v:now u:nex continue for d,u,pp in E[v]: if p>pp: continue tmp=d+cost[v] if tmpX: print(-1) exit() ok,ng=0,10**9+1 while (ng-ok)>1: mid=(ok+ng)//2 A=dijkstra(0,mid) if A[-1]>X: ng=mid else: ok=mid print(ok) main()