환상적인 신호등 여행

밥(Bob)은 중소 도시의 교통과에서 일한다. 그는 도시의 교통 신호등을 관리하고 필요할 때 수리반을 보내는 일을 맡고 있다. 여유 시간이 많은 그는 도시 곳곳을 오가는 짧은 이동의 최단 시간 경로를 알아내려 한다. 밥은 거리의 배치와 모든 신호등의 위치·주기를 알고 있으며, 문제를 단순화하기 위해 다음과 같이 가정한다.

1. 모든 자동차는 같은 최고 속도로 달린다. 빨간불에 멈춰 있던 차는 반응하여 다시 속도를 내는 데 5초가 걸린다. (즉, 차가 5초 동안은 사실상 정지해 있다가 그 후 최고 속도로 나아간다. 또한 그 5초 동안 신호가 다시 빨간불로 바뀌지는 않는다고 가정한다.)
2. 각 자동차는 최고 속도로 신호등에 접근하여, 초록불이거나 노란불이면 통과하고, 빨간불이면 즉시 멈춘다. 신호가 초록불로 바뀌는 바로 그 순간에 도착하면 통과할 수 있다. 신호가 빨간불로 바뀌는 바로 그 순간에 도착하면 반드시 멈춰야 한다.
3. 신호등에서 회전하는 데 걸리는 시간은 무시한다. 어떤 두 신호등 사이도 (직접은 아닐 수 있으나) 이동이 가능하다.

또한 U턴은 허용되지 않으며, 경로는 같은 교차로를 다시 방문하지 않는다. 밥이 최단 시간 경로를 찾도록 도와라.

초록·노랑·빨강 지속 시간이 각각 $g$, $y$, $r$인 신호등의 주기 길이는 $g + y + r$이다. 모든 신호등은 시각 0에 초록불 구간을 시작한다. 한 주기 안에서 $[0, g)$초는 초록불, $[g, g+y)$초는 노란불, $[g+y, g+y+r)$초는 빨간불이며, 이후 주기가 반복된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 네 양의 정수 $n$, $m$, $s$, $e$가 주어진다. $n$ ($2 \le n \le 100$)은 신호등의 수(0번부터 $n-1$번까지 번호가 매겨져 있다), $m$은 신호등을 잇는 도로의 수, $s$와 $e$ ($s \ne e$)는 이동의 시작 신호등과 도착 신호등이다.

이어지는 $n$개의 줄은 각각 g y r 형식이며, 그 신호등이 초록불, 노란불, 빨간불인 시간(초)을 나타낸다 ($1 \le g, y, r \le 100$). 이 줄들 중 첫 번째는 0번 신호등, 두 번째는 1번 신호등에 대한 것이며 이런 식으로 계속된다.

그다음 $m$개의 줄은 각각 하나의 도로를 l1 l2 t 형식으로 설명한다. 여기서 l1, l2는 도로가 잇는 두 신호등이고, $t$는 최고 속도로 그 도로를 달리는 데 걸리는 시간(초, $t \le 500$)이다. 정지 상태에서 그 도로를 출발할 때의 이동 시간은 이 값에 $5$를 더하면 된다. 모든 도로는 양방향이다.

시각 0에 모든 신호등은 막 초록불 구간을 시작하고, 당신의 차는 신호등 $s$에 정지해 있다. 출발하는 데 5초가 걸리므로 $g + y$가 5 이하인 경우는 없다고 가정해도 된다. 마지막 테스트 케이스 다음에는 0 0 0 0이 있는 줄이 오며 입력이 끝난다.

각 테스트 케이스마다, 시작 신호등에서 도착 신호등까지 가는 최단 시간을 mm:ss 형식(분과 초)으로 한 줄에 출력한다. 초가 10보다 작으면 앞에 0을 붙인다(예: 4:5가 아니라 4:05). 분이 10보다 작으면 한 자리로만 출력한다(4:05처럼).