해적의 길

잭 스패로 선장이 또다시 원주민들의 섬에 갇혔습니다. 원주민들은 그를 다시 신이라고 믿고 있지만, 잭은 (목숨이 걸린 만큼) 쉽게 포기하지 않고 탈출을 시도합니다.

섬은 수많은 강으로 가로막혀 여러 구역으로 나뉘어 있습니다. 두 구역은 다리로 연결되어 있을 때에만 인접합니다. 잭은 자신이 갇혀 있는 구역에서, 그의 사랑하는 배 블랙 펄이 정박해 있는 구역까지 가야 합니다.

원주민들은 자신들의 "신"을 섬에 붙잡아 두고 싶어 일부 다리에 감시병을 배치했으며, 감시하는 다리 하나당 정확히 한 명씩입니다. 잭은 불필요한 수고를 들이기 싫고(또한 신도들에게 자비를 베풀고 싶어) 블랙 펄까지 가는 길에서 되도록 가장 적은 수의 감시병만 제압하려 합니다. 그 최소 감시병 수를 구하세요.

첫 줄에는 공백 하나로 구분된 정수 네 개가 주어집니다:

n b s e

여기서 $n$은 구역의 수, $b$는 다리의 수, $s$ ($0 \le s \lt n$)는 잭이 갇혀 있는 구역, $e$ ($0 \le e \lt n$)는 블랙 펄이 있는 구역입니다.

이어지는 $b$개의 줄은 각각 다리 하나를 공백 하나로 구분된 정수 세 개로 나타냅니다:

a b c

여기서 $a$와 $b$ ($0 \le a, b \lt n$)는 그 다리가 연결하는 두 구역이고, $c$는 $0$ 또는 $1$로 다리가 감시되는지($1$) 아닌지($0$)를 나타냅니다. 감시되는 다리에는 감시병이 정확히 한 명 있습니다.

잭이 있는 구역에서 블랙 펄이 있는 구역으로 가는 경로가 없을 수도 있습니다. 그런 경우에는 다음 한 줄을 정확히 출력합니다:

It's over with Captain Jack. At least till Pirates of the Caribbean 3.

경로가 있는 경우에는 다음 한 줄을 정확히 출력합니다:

x native(s) on the easiest way for Captain Jack.

여기서 x는 시작 구역에서 블랙 펄이 있는 구역까지의 어떤 경로에서든 감시병의 최소 수입니다.