Courier Services

The company SuperCourier delivers parcels to any corner of the world. The company has a network of $n$ offices numbered from $1$ to $n$. Each office collects parcels from a designated area, sorts them, transfers them, and delivers them to recipients. Fixed connections between offices allow parcels to be transported.

Offices are divided into classes A, B, and C. The network has $n_A$ class-A offices, $n_B$ class-B offices, and $n_C$ class-C offices, where $n_A + n_B + n_C = n$, $n_A > 0$, and $n_C > 0$.

• Class-A offices perform primary sorting and transfer. Every parcel, on its way from sender to recipient, must pass through at least one class-A office. A class-A office is connected to every other class-A office, and to some number of class-B and class-C offices.
• Class-B offices perform secondary sorting and transfer. Every class-B office is connected to at least one class-A office and to some number of class-C offices; it has no connection to any other class-B office.
• Class-C offices only collect parcels from their area and deliver parcels to recipients in that area. Every class-C office has exactly one connection, to a class-A or class-B office.

The figure below shows an example network.

Figure: An example network of offices.

Each office and each connection is assigned a pair of attributes ($cost$, $time$). For an office, this pair gives the cost and time of collecting or delivering a parcel in the area it serves, and of sorting and transferring parcels, depending on the office class. For a connection, the pair gives the cost and time of transporting a parcel between the two offices.

The task is to determine, for a given network, the best routes for transporting parcels from a given start office $s$ to a given destination office $t$ (both $s$ and $t$ are class C). Each route is characterized by a pair of attributes, its transport cost and time: these are the sum of the costs and the sum of the times of all offices and connections along the route (including $s$ and $t$; an office or connection visited several times is counted each time). The smaller the cost and the shorter the time, the better. We say one route is better than another if it has:

• a smaller cost and a not-longer time, or
• a shorter time and a not-larger cost.

We are interested in the routes for which no better route exists.

For example (see the figure), let $s = C_1$ and $t = C_2$. To choose the best transport routes between these offices we consider the routes $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$, and $C_1 \to B_4 \to A_6 \to A_3 \to B_4 \to C_2$, with (cost, time) pairs $(55, 66)$, $(60, 65)$, $(84, 95)$, and $(84, 95)$ respectively. The first two routes are better than the third and the fourth. So there are two routes for which no better route exists: $C_1 \to B_4 \to A_3 \to B_4 \to C_2$ and $C_1 \to B_4 \to A_6 \to B_4 \to C_2$.

Write a program that:

• reads the description of the office network together with the start office $s$ and the destination office $t$,
• determines all (cost, time) pairs characterizing the transport routes from $s$ to $t$ for which no better route exists, where if at least two different routes give the same (cost, time) pair it is reported only once,
• prints the determined pairs.

The first line contains two positive integers separated by a single space: the number of offices $n$ and the number of connections $m$, where $2 \le n \le 1000$ and $1 \le m \le 5000$. Offices are numbered from $1$ to $n$.

Each of the next $n$ lines describes one office. The description consists of a letter A, B, or C, and two positive integers $k$ and $c$, separated by single spaces. The value $k$ is the cost and $c$ is the time of sorting parcels at the office, where $1 \le k \le 20$ and $1 \le c \le 20$.

Each of the next $m$ lines describes one connection between offices. The description consists of four integers $a$, $b$, $k$, and $c$, separated by single spaces. The numbers $a$ and $b$ are the numbers of the connected offices, $1 \le a, b \le n$. The value $k$ is the cost and $c$ is the time of transporting a parcel over this connection, $1 \le k \le 100$ and $1 \le c \le 100$. All connections are bidirectional. There is at most one (direct) connection between any two offices.

The last line contains two positive integers $s$ and $t$ separated by a single space, $1 \le s, t \le n$. These are the numbers of the start and destination offices.

The first line should contain one positive integer $r$: the number of distinct (cost, time) pairs characterizing all transport routes from office $s$ to office $t$ for which no better route exists. The next $r$ lines should contain these pairs, in order of increasing cost. Each pair should be printed on a separate line, with the cost and the time separated by a single space.