시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 502 210 165 44.355%

문제

매일 아침, 세준이는 학교에 가기 위해서 D킬로미터의 거리의 고속 도로를 차를 타고 운전해서 간다. 정말 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게되었다. 지름길의 정보는 다음과 같이 주어진다.

S E L 형식으로 주어지는데 고속도로의 S킬로미터 구역에서 E킬로미터 구역까지 한번에 갈 수 있는 지름길의 길이가 L이란 소리다. 모든 지름길은 일방통행이다. 그리고, 고속도로를 역주행할 수는 없다.

입력

첫째 줄에 지름길의 개수 N과 세준이가 운전해야하는 길이 D가 주어진다. 둘째 줄부터 N개의 줄에 지름길의 시작, 끝, 길이가 주어진다. D는 10,000보다 작거나 같은 자연수이고, 지름길의 정보는 모두 10,000보다 작거나 같은 음이아닌 정수이다. 지름길의 시작은 반드시 끝보다 작다.

출력

입력으로 D와 지름길의 정보가 주어지면, 세준이가 운전해야하는 거리의 최소값을 출력하시오.

예제 입력

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

예제 출력

70

힌트

출처