31829번 - 첫 차 타기

문제

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

제한

힌트