리조트

바이트 산맥에는 바이트가리(Bytegary)라는 스키 리조트가 있다. 이곳은 크로스컨트리 스키 코스로 유명하다. 모든 코스와 리프트는 각각 어떤 빈터(clearing)에서 시작해 다른 빈터에서 끝난다.

• 스키 코스(track)는 방향이 있는 간선이며 이용하는 데 비용이 들지 않는다. 양방향 코스는 서로 반대 방향의 단방향 코스 두 개로 표현된다.
• 리프트(lift)는 방향이 있는 간선이며, 한 번 타면 자기 자석 카드에서 정해진 점수만큼 차감된다. 쓰지 않고 남은 점수는 환불되지 않는다. 양방향 리프트도 방향별로 하나씩, 단방향 리프트 두 개로 표현되며 두 방향의 비용은 서로 다를 수 있다.

바이트오니(Byteoni)는 지금 빈터 $b$에 있고, 마지막 카드에 점수 $s$가 남아 있다. 그는 바이트가리 기슭에 있는 기지 빈터(base clearing, 번호 $1$부터 $n'$까지) 중 하나로 내려가려 하며, 그때 카드에 남는 점수를 최소로 만들고 싶어 한다.

그는 어떤 코스든 자유롭게(비용 없이) 탈 수 있고, 현재 점수가 리프트 비용 이상일 때에 한해 그 리프트를 탈 수 있다. 기지 빈터에 도달하는 것은 항상 가능하다고 가정해도 된다(점수가 모자라 산에 갇히는 경우는 없다).

바이트오니가 기지 빈터에 도착했을 때 카드에 남을 수 있는 점수의 최솟값을 구하여라.

• 첫째 줄에 두 정수 $n$과 $n'$이 공백 하나로 구분되어 주어진다 ($1 \le n' < n \le 1000$). $n$은 전체 빈터의 수이며, 빈터는 $1$부터 $n$까지 번호가 매겨진다. 기지 빈터는 번호 $1$부터 $n'$까지이다.
• 둘째 줄에 스키 코스의 개수 $k$가 주어진다 ($1 \le k \le 5000$).
• 다음 $k$개의 줄에는 각각 서로 다른 두 정수 $p_1$, $p_2$가 주어지며 ($1 \le p_1 \ne p_2 \le n$), $p_1$에서 $p_2$로 가는 단방향 코스를 뜻한다.
• 그다음 줄에 리프트의 개수 $m$이 주어진다 ($1 \le m \le 300$).
• 다음 $m$개의 줄에는 각각 세 정수 $q_1$, $q_2$, $r$가 주어지며 ($1 \le q_1 \ne q_2 \le n$, $1 \le r \le 1000$), $q_1$에서 $q_2$로 가고 $r$점을 소모하는 단방향 리프트를 뜻한다.
• 마지막 줄에 두 정수 $b$와 $s$가 주어진다 ($1 \le b \le n$, $1 \le s \le 2000$). $b$는 바이트오니가 있는 빈터의 번호, $s$는 마지막 카드에 남은 점수이다.

바이트오니가 기지 빈터에 도착했을 때 카드에 남을 수 있는 점수의 최솟값을 한 줄에 정수 하나로 출력한다.