자카르타 교통 체증

자카르타의 교통은 매우 혼잡하다. 출퇴근 혼잡 시간대(러시아워)에는 거리가 정체되어, 그 시간 동안에는 평소 속도의 절반으로만 달릴 수 있다. 따라서 약속에 늦지 않으려면 이동 계획을 신중히 세워야 한다.

예를 들어 지점 P에서 지점 Q까지 가는 도로가 평소에는 $20$분 걸리고, 이 도로가 15:00부터 16:00까지 정체된다고 하자. 러시아워와 관련된 몇 가지 상황을 살펴보자.

1. 러시아워가 시작되기 $15$분 전(즉 14:45)에 P에서 출발하면, 정체가 시작되기 전까지 평소 속도로 $15$분어치 거리를 이동한다. 남은 거리는 평소 기준 $5$분어치인데, 정체 중에는 속도가 절반이므로 통과하는 데 $10$분이 걸린다. 따라서 P에서 Q까지 총 $15 + 10 = 25$분이 걸린다.
2. 러시아워가 끝나기 직전 $5$분(즉 15:55)에 출발하면, 정체 중인 처음 $5$분 동안 이동한 거리는 평소 속도로 $2.5$분어치에 해당한다. 남은 거리는 평소 기준 $17.5$분어치이고 이제 정체가 풀렸으므로 $17.5$분이 더 걸린다. 따라서 총 $5 + 17.5 = 22.5$분이 걸린다.
3. 위 상황들의 다른 조합도 가능하다.

즉, 어떤 순간에 정체 시간대인 도로를 달리고 있으면 그 순간에는 절반 속도로 이동하고, 그 외에는 평소 속도로 이동한다. 각 도로의 러시아워는 하루 안에서만 정의되며 자정을 넘겨 이어지지 않는다.

교차로가 최대 $N$개, 도로가 $M$개인 지도가 주어진다. 출발 지점 $s$에서 목적지 $d$까지 가는 데 걸리는 최소 시간을 분 단위로 구하여라. 도중에 멈추어 기다리지 않고 곧바로 이동한다고 가정한다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $N$ ($1 \le N \le 20$)과 $M$이 주어진다. $N$은 교차로의 수, $M$은 도로의 수이다. 교차로는 $0$번부터 번호가 매겨진다.

이어지는 $M$개의 줄에는 각 도로의 정보가 주어진다. 각 줄은 세 정수 $P$, $Q$, $T$ ($1 \le T \le 50$)로 시작하며, 이는 교차로 $P$와 교차로 $Q$를 잇는 도로가 있고 평소에 이 도로를 지나는 데 $T$분이 걸린다는 뜻이다(도로는 양방향이다). 세 정수 뒤에는 문자 N 또는 R이 온다. N은 그 도로에 러시아워가 없다는 뜻이며 뒤에 다른 값이 오지 않는다. R 뒤에는 러시아워의 시작 시각과 종료 시각이 hh:mm 형식(00:00부터 23:59까지)으로 주어진다. 러시아워는 자정을 넘겨 이어지지 않는다.

각 테스트 케이스의 마지막 줄에는 출발 지점 $s$, 목적지 $d$, 그리고 현재 시각 $w$가 hh:mm 형식으로 주어진다.

입력의 끝은 두 개의 $0$으로 이루어진 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 $s$에서 $d$까지 가는 데 필요한 최소 시간을 분 단위로 한 줄에 출력한다. 소수점 아래 두 자리까지 항상 출력한다.