택배 서비스

슈퍼쿠리어(SuperKurier) 회사는 세계 어느 곳으로든 소포를 배송한다. 이 회사는 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 영업소로 이루어진 네트워크를 가지고 있다. 각 영업소는 담당 구역에서 소포를 수거하고, 분류하고, 환적하고, 수취인에게 배달한다. 영업소들 사이에는 소포를 운송할 수 있는 고정 연결이 유지된다.

영업소는 A, B, C 세 등급으로 나뉜다. 네트워크에는 A등급 영업소가 $n_A$개, B등급 영업소가 $n_B$개, C등급 영업소가 $n_C$개 있으며, $n_A + n_B + n_C = n$, $n_A > 0$, $n_C > 0$을 만족한다.

• A등급 영업소에서는 주 분류와 환적이 이루어진다. 모든 소포는 발송인에서 수취인에 이르는 경로에서 반드시 하나 이상의 A등급 영업소를 거쳐야 한다. A등급 영업소는 다른 모든 A등급 영업소와 연결되어 있고, 일부 B등급 및 C등급 영업소와도 연결된다.
• B등급 영업소에서는 2차 분류와 환적이 이루어진다. 각 B등급 영업소는 하나 이상의 A등급 영업소와 연결되고 일부 C등급 영업소와 연결되지만, 다른 B등급 영업소와는 연결되지 않는다.
• C등급 영업소는 담당 구역에서 소포를 수거하고 그 구역의 수취인에게 소포를 배달하는 일만 한다. 각 C등급 영업소는 A등급 또는 B등급 영업소와 정확히 하나의 연결만 가진다.

아래 그림은 영업소 네트워크의 예시이다.

그림: 영업소 네트워크의 예시.

각 영업소와 각 연결에는 (비용, 시간) 속성 쌍이 부여된다. 영업소의 경우 이 쌍은 등급에 따라 담당 구역에서 소포를 수거하거나 배달하는 것, 그리고 소포를 분류하고 환적하는 것에 드는 비용과 시간을 나타낸다. 연결의 경우 이 쌍은 두 영업소 사이에서 소포를 운송하는 데 드는 비용과 시간을 나타낸다.

문제는 주어진 네트워크에서 주어진 출발 영업소 $s$부터 도착 영업소 $t$까지(두 영업소 $s$와 $t$는 모두 C등급이다) 소포를 운송하는 가장 좋은 경로들을 찾는 것이다. 각 경로는 운송 비용과 시간이라는 속성 쌍으로 특징지어진다. 이는 경로 위에 있는 모든 영업소와 연결의 비용의 합, 그리고 시간의 합이다($s$와 $t$ 포함). 같은 영업소나 연결을 여러 번 지나면 그때마다 각각 더해진다. 비용이 작을수록, 시간이 짧을수록 좋다. 한 경로가 다른 경로보다 더 좋다는 것은 다음 중 하나를 의미한다:

• 비용이 더 작으면서 시간이 더 길지 않거나,
• 시간이 더 짧으면서 비용이 더 크지 않다.

우리는 그보다 더 좋은 경로가 존재하지 않는 경로들에 관심이 있다.

예를 들어 (그림 참고) $s = C_1$, $t = C_2$라고 하자. 이 두 영업소 사이의 가장 좋은 운송 경로를 고르기 위해 다음 경로들을 살펴본다: $C_1 \to B_4 \to A_3 \to B_4 \to C_2$, $C_1 \to B_4 \to A_6 \to B_4 \to C_2$, $C_1 \to B_4 \to A_3 \to A_6 \to B_4 \to C_2$, $C_1 \to B_4 \to A_6 \to A_3 \to B_4 \to C_2$. 각각의 (비용, 시간) 쌍은 순서대로 $(55, 66)$, $(60, 65)$, $(84, 95)$, $(84, 95)$이다. 처음 두 경로는 세 번째와 네 번째 경로보다 더 좋다. 따라서 그보다 더 좋은 경로가 존재하지 않는 운송 경로는 두 개이다: $C_1 \to B_4 \to A_3 \to B_4 \to C_2$와 $C_1 \to B_4 \to A_6 \to B_4 \to C_2$.

다음을 수행하는 프로그램을 작성하라:

• 영업소 네트워크의 설명과 출발 영업소 $s$, 도착 영업소 $t$를 입력받고,
• $s$에서 $t$까지의 운송 경로 중 그보다 더 좋은 경로가 존재하지 않는 것들을 특징짓는 모든 (비용, 시간) 쌍을 구하되, 서로 다른 두 개 이상의 경로가 같은 (비용, 시간) 쌍을 주면 그 쌍은 한 번만 출력하고,
• 구한 쌍들을 출력한다.

첫째 줄에는 하나의 공백으로 구분된 두 양의 정수가 있다. 영업소의 수 $n$과 연결의 수 $m$이며, $2 \le n \le 1000$, $1 \le m \le 5000$이다. 영업소는 $1$번부터 $n$번까지 번호가 매겨진다.

다음 $n$개의 줄에는 각 영업소가 한 줄에 하나씩 설명된다. 각 영업소의 설명은 문자 A, B, C 중 하나와, 하나의 공백으로 구분된 두 양의 정수 $k$, $c$로 이루어진다. $k$는 그 영업소에서 소포를 분류하는 비용이고 $c$는 시간이며, $1 \le k \le 20$, $1 \le c \le 20$이다.

다음 $m$개의 줄에는 영업소 사이의 연결이 한 줄에 하나씩 설명된다. 각 연결의 설명은 하나의 공백으로 구분된 네 정수 $a$, $b$, $k$, $c$로 이루어진다. $a$와 $b$는 연결된 두 영업소의 번호이며 $1 \le a, b \le n$이다. $k$는 그 연결로 소포를 운송하는 비용이고 $c$는 시간이며, $1 \le k \le 100$, $1 \le c \le 100$이다. 모든 연결은 양방향이다. 임의의 두 영업소 사이에는 (직접) 연결이 최대 하나 있다.

마지막 줄에는 하나의 공백으로 구분된 두 양의 정수 $s$와 $t$가 있으며 $1 \le s, t \le n$이다. 이는 출발 영업소와 도착 영업소의 번호이다.

첫째 줄에는 하나의 양의 정수 $r$을 출력한다. 이는 영업소 $s$에서 $t$까지의 모든 운송 경로 중 그보다 더 좋은 경로가 존재하지 않는 것들을 특징짓는 서로 다른 (비용, 시간) 쌍의 개수이다. 다음 $r$개의 줄에는 그 쌍들을 비용이 증가하는 순서로 출력한다. 각 쌍은 별도의 줄에 출력하며, 비용과 시간은 하나의 공백으로 구분한다.