첫 차 타기

세우는 현재 $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$번 건물에 도착하는 데 걸리는 최소 시간을 출력한다.