데이트 픽업

리처드와 재닛은 첫 데이트를 한다. 리처드는 자전거를 타고 집으로 그녀를 데리러 가겠다고 제안했다. 재닛은 10분에서 20분 뒤 준비가 되면 전화하겠다고 말했다. 리처드는 성격이 급하다. 그는 집에서 그녀의 신호를 기다릴 수도 있고, 일찍 나가 동네를 돌다가 그녀가 전화했을 때 최대한 빨리 도착할 수도 있다. 자전거에 오르면 그는 법정 속도보다 느리게 달리지 않고, 교차로에서 멈추지 않으며, 재닛의 집 앞에서 기다리지도 않는다. 다만 그녀의 집 앞을 지나쳤다가 나중에 돌아오는 것은 상관없다.

동네는 방향이 있는 그래프로 주어진다. 리처드는 자기 집에서 선택적으로 기다린 뒤 경로를 정해, 재닛이 최악의 경우에 기다리는 시간을 최소화하려고 한다. 그는 원하는 만큼 오래 이동할 수 있고, 각 교차로를 원하는 만큼 몇 번이든 방문할 수 있다.

재닛은 준비가 되자마자 리처드에게 전화하고, 리처드는 그때부터 그녀에게 가는 가장 짧은 경로를 택한다. 리처드는 준비 시각을 정확히 알지 못하고, 그것이 $a$분에서 $b$분 사이라는 것만 안다. 시각은 정수 분이 아닐 수도 있다.

리처드가 교차로를 지나는 바로 그 순간 전화가 오면, 전화가 먼저 일어난 것으로 본다. 즉 리처드는 전화를 듣고 나서 교차로에서 다음 행동을 고를 수 있다. 예를 들어 그녀의 집 앞을 지나는 중에 전화가 오면 그는 바로 그곳에 멈출 수 있고, 재닛은 전혀 기다리지 않는다.

재닛이 $w$분을 기다리지 않을 수도 있지만, 리처드가 교차로를 막 떠난 직후처럼 나쁜 순간에 전화하면 임의로 작은 $\varepsilon > 0$에 대해 $w - \varepsilon$분을 기다릴 수 있다. 이 경우에도 최악의 대기 시간은 $w$로 본다.

첫 줄에 정수 $a$와 $b$가 주어진다($0 \le a \le b \le 10^{12}$). 재닛은 최소 $a$분, 최대 $b$분 뒤에 준비가 된다는 뜻이다.

둘째 줄에 정수 $n$과 $m$이 주어진다($2 \le n \le m \le 10^5$). 각각 교차로의 수와 도로의 수이다. 교차로는 1번부터 $n$번까지 번호가 매겨져 있다.

이어서 $m$개의 줄에 정수 $u$, $v$, $t$가 주어진다($1 \le u, v \le n$, $1 \le t \le 10^6$). 이는 $u$에서 $v$로 가는 일방통행 도로가 있고, 이동에 정확히 $t$분이 걸린다는 뜻이다.

리처드의 집은 1번 교차로, 재닛의 집은 $n$번 교차로이다. 리처드의 집에서 재닛의 집으로 갈 수 있고, 각 교차로에서는 나가는 도로가 적어도 하나 있다. 자기 자신으로 돌아오는 도로일 수도 있다.

재닛이 $a$분에서 $b$분 사이에 준비된다고 할 때, 리처드가 경로를 최적으로 계획한 경우 재닛이 기다리는 최악의 시간을 출력한다.

최악의 대기 시간은 항상 정수이다.