신호등

케노샤(Kenosha) 시에는 $N$개의 교차로가 있으며 $1 \ldots N$로 번호가 매겨져 있고, 이들을 잇는 $M$개의 도로가 $1 \ldots M$로 번호가 매겨져 있다. 같은 교차로 쌍을 잇는 도로는 둘 이상 존재하지 않으며, 자기 자신을 잇는 도로도 없다. 교차로 $i$와 $j$ 사이의 정수 이동 시간 $T_{ij}$는 양방향으로 동일하다. 즉 $T_{ij} = T_{ji}$이다.

각 교차로에는 신호등이 하나씩 있으며 파란색 또는 보라색 두 가지 색 중 하나를 나타낸다. 각 신호등은 일정 시간 동안 파란색을 켰다가 다른 일정 시간 동안 보라색을 켜는 것을 주기적으로 반복한다. 어떤 도로로 출발하는 바로 그 순간에 그 도로 양 끝 두 교차로의 신호등 색이 같을 때에만 그 도로로 진입할 수 있다. 이동하는 도중에 두 신호등의 색이 계속 같을 필요는 없다.

차량이 신호가 바뀌는 바로 그 순간에 교차로에 도착하면 새 색을 따른다. 차량은 교차로에서 원하는 만큼 대기할 수 있다. 각 교차로 $i$에 대해 파란색 지속 시간 $DB_i$, 보라색 지속 시간 $DP_i$, 초기 색 $C_i$(파란색이면 B, 보라색이면 P), 그리고 그 초기 색이 처음으로 바뀌기까지 남은 시간 $R_i$가 주어진다.

시각 $0$에 출발 교차로 $S$에서 출발하여, 도착 교차로 $D$($D \ne S$)에 이르는 최소 시간을 구하여라.

제약 조건: $2 \le N \le 300$, $1 \le M \le 14{,}000$, $1 \le T_{ij} \le 100$, $1 \le DB_i \le 100$, $1 \le DP_i \le 100$, $1 \le R_i \le 100$, $1 \le S, D \le N$.

예시 설명. 교차로 4개와 도로 5개가 있고, 차량이 교차로 1에서 교차로 4로 가려는 상황을 생각하자.

도로(이동 시간): 1-2 (4), 1-3 (40), 2-3 (75), 2-4 (76), 3-4 (77).

최소 시간은 경로 1 -> 2 -> 4를 따라 127이다.

• 교차로 1은 파란색으로 시작하지만 교차로 2는 보라색이므로, 차량은 교차로 1이 보라색으로 바뀔 때까지 2초 대기한 뒤 4초 동안 이동하여 시각 6에 교차로 2에 도착한다.
• 시각 6에 교차로 2가 파란색으로 바뀌지만, 교차로 4는 32초 더 보라색을 유지한다. 그 32초가 지나면 교차로 2가 보라색으로 바뀌는 순간에 교차로 4가 파란색으로 바뀌므로 여전히 색이 다르다. 차량은 교차로 2가 파란색이 될 때까지 13초 더 대기한다. 이제 둘 다 파란색이므로 76초 동안 이동하여 교차로 4에 도착한다.
• 총 시간: $2 + 4 + 32 + 13 + 76 = 127$초.

• 첫째 줄: 두 정수 $S$와 $D$가 공백으로 구분되어 주어진다.
• 둘째 줄: 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다.
• 3번째 줄부터 $N+2$번째 줄까지: $i+2$번째 줄은 교차로 $i$를 나타내며, 문자 하나와 정수 셋이 공백 하나로 구분되어 $C_i$, $R_i$, $DB_i$, $DP_i$ 순서로 주어진다.
• $N+3$번째 줄부터 $N+M+2$번째 줄까지: $N+2+k$번째 줄은 도로 $k$를 나타내며, 세 정수 $i$, $j$, $T_{ij}$가 주어진다.

• 첫째 줄: 출발 교차로에서 도착 교차로까지의 최소 시간을 나타내는 정수 하나를 출력한다. 경로가 존재하지 않으면 $0$을 출력한다.