첫 차 타기

현재 $1$번 건물에 있는 세우는 막차를 놓쳐버렸다. 그래서 세우네 집인 $N$번 건물까지 걸어가기로 했다. 그러다 세우는 $1$번 건물에서 출발할 때, 지금부터 정확히 $K$분 후부터 버스 첫 차가 운행하기 시작한다는 것을 깨달았다.

세우네 도시에는 양방향으로 서로 다른 두 개의 건물을 연결하는 $X$개의 인도와 $Y$개의 차도가 있다. 첫 차가 운행하기 시작하는 $K$분 이전에는 인도로만 이동할 수 있고, $K$분 후부터는 인도로 이동하거나, 버스를 타고 차도로 이동할 수 있다.

세우가 $1$번 건물에서 출발해 $N$번 건물까지 도착하는 데 걸리는 최소 시간을 구하는 프로그램을 작성해 보자.

첫 번째 줄에 각각 건물의 개수, 버스 첫 차가 운행하기 시작하는 시간, 인도의 개수, 차도의 개수를 의미하는 정수 $N$, $K$, $X$, $Y$가 공백으로 구분되어 주어진다. $(3 \leq N \leq 200 \ 000$; $1 \leq X$, $Y \leq 200 \ 000$; $1 \leq K \leq 10^9)$

$X$개의 줄에 걸쳐, $1 + i$번째 줄에는 각각 $i$번째 인도가 연결하는 두 건물과 이동 시간을 뜻하는 정수 $s_i$, $e_i$, $d_i$가 공백으로 구분되어 주어진다. 임의의 $i$에 대해 $s_i$번 건물에서 $e_i$번 건물로 가는 인도는 유일하다. $(1 \leq s_i$, $e_i \leq N$; $s_i \neq e_i$; $1 \leq d_i \leq 10^9)$

$Y$개의 줄에 걸쳐, $X + 1 + i$번째 줄에는 각각 $i$번째 차도가 연결하는 두 건물과 이동 시간을 뜻하는 정수 $s_i$, $e_i$, $d_i$가 공백으로 구분되어 주어진다. 임의의 $i$에 대해 $s_i$번 건물에서 $e_i$번 건물로 가는 차도는 유일하다. $(1 \leq s_i$, $e_i \leq N$; $s_i \neq e_i$; $1 \leq d_i \leq 10^9)$

세우가 $1$번 건물에서 출발하여 $N$번 건물까지 도착할 수 있음이 보장된다.

첫 번째 줄에 $1$번 건물에서 출발해 $N$번 건물까지 도착하는 데 걸리는 최소 시간을 출력한다.