Firma SuperKurier oferuje dostarczanie przesyłek w dowolny zakątek świata. Firma ma sieć n placówek ponumerowanych od 1 do n. W placówkach następuje zbieranie przesyłek z określonego obszaru, ich sortowanie, przeładunek oraz dostarczanie odbiorcom. Pomiędzy placówkami utrzymywane są stałe połączenia umożliwiające transport przesyłek. Placówki podzielone są na klasy A, B i C. W sieci znajduje się n_A placówek klasy A, n_B placówek klasy B oraz n_C placówek klasy C, przy czym n_A + n_B + n_C = n, n_A > 0, n_C > 0. W placówkach klasy A odbywa się sortowanie zasadnicze oraz przeładunek przesyłek. Każda przesyłka na swej drodze od nadawcy do odbiorcy musi przejść przez co najmniej jedną placówkę klasy A. Placówki klasy A mają połączenia ze wszystkimi pozostałymi placówkami klasy A oraz z pewną liczbą placówek klasy B i C. W placówkach klasy B odbywa się sortowanie wtórne oraz przeładunek przesyłek. Każda placówka klasy B ma połączenia z co najmniej jedną placówką klasy A oraz z pewną liczbą placówek klasy C, nie ma natomiast połączeń z innymi placówkami klasy B. Zadaniem placówek klasy C jest jedynie odbieranie przesyłek z określonego obszaru i dostarczanie przesyłek do odbiorców na tym obszarze. Każda placówka klasy C ma tylko jedno połączenie z placówką klasy A lub B. Poniższy rysunek przedstawia przykładową sieć placówek.</p>

Rysunek: Przykładowa sieć placówek.

Placówkom oraz połączeniom są przyporządkowane pary atrybutów (koszt, czas). Dla placówek para ta wyznacza koszt oraz czas odebrania lub doręczenia przesyłki na obszarze obsługiwanym przez placówkę, a także sortowania i przeładunku przesyłek, w zależności od klasy placówki. Para atrybutów przypisana połączeniu oznacza koszt i czas przewiezienia przesyłki pomiędzy placówkami.

Zadanie polega na wyznaczeniu dla danej sieci najlepszych tras transportu przesyłek z danej placówki początkowej s, do danej placówki docelowej t (placówki s i t są klasy C). Każda trasa charakteryzuje się parą atrybutów, kosztem oraz czasem transportu: są to sumy kosztów i czasów, placówek i połączeń znajdujących się na trasie (łącznie z s i t). Im mniejszy koszt i krótszy czas transportu, tym lepiej. Powiemy, że jedna trasa jest lepsza od drugiej, jeśli charakteryzuje się:

• mniejszym kosztem i nie dłuższym czasem, lub
• krótszym czasem i nie większym kosztem.

Interesują nas takie trasy, od których nie ma lepszych.

Na przykład, niech s = C₁ oraz t = C₂ (por. rysunek). Chcąc wybrać najlepsze trasy transportu przesyłek pomiędzy tymi placówkami rozważamy następujące trasy: C₁ → B₄ → A₃ → B₄ → C₂, C₁ → B₄ → A₆ → B₄ → C₂, C₁ → B₄ → A₃ → A₆ → B₄ → C₂ oraz C₁ → B₄ → A₆ → A₃ → B₄ → C₂ o parach (koszt, czas) odpowiednio: (55, 66), (60, 65), (84, 95) i (84, 95). Pierwsze dwie trasy są lepsze niż trzecia i czwarta. Tak więc, mamy dwie trasy transportu przesyłek, od których nie ma lepszych: C₁ → B₄ → A₃ → B₄ → C₂ i C₁ → B₄ → A₆ → B₄ → C₂.

Napisz program, który:

• wczyta opis sieci placówek oraz placówkę początkową s i docelową t,
• wyznaczy wszystkie pary (koszt, czas) charakteryzujące te trasy transportu przesyłek z s do t, od których nie ma lepszych, przy czym jeżeli co najmniej 2 różne trasy dają tę samą parę (koszt, czas), to należy ją wypisać 1 raz,
• wypisze wyznaczone pary.

W pierwszym wierszu zapisane są dwie dodatnie liczby całkowite oddzielone pojedynczym odstępem: liczba placówek n oraz liczba połączeń m, 2 ≤ n ≤ 1000, 1 ≤ m ≤ 5000. Placówki są ponumerowane od 1 do n. W kolejnych n wierszach opisane są kolejne placówki, po jednej w wierszu. Opis każdej placówki składa się z litery A, B lub C, oraz dwóch dodatnich liczb całkowitych k i c, pooddzielanych pojedynczymi odstępami. Liczba k oznacza koszt, a c czas sortowania przesyłek w placówce, 1 ≤ k ≤ 20, 1 ≤ c ≤ 20.

W kolejnych m wierszach opisane są połączenia między placówkami, po jednym w wierszu. Opis każdego z połączeń składa się z czterech liczb całkowitych a, b, k i c, pooddzielanych pojedynczymi odstępami. Liczby a i b, to numery połączonych placówek, 1 ≤ a, b ≤ n. Liczba k to koszt, a c to czas transportu przesyłki danym połączeniem, 1 ≤ k ≤ 100, 1 ≤ c ≤ 100. Wszystkie połączenia są dwukierunkowe. Między każdymi dwiema placówkami mamy co najwyżej jedno (bezpośrednie) połączenie.

W ostatnim wierszu zapisane są dwie dodatnie liczby całkowite s i t, oddzielone pojedynczym odstępem, 1 ≤ s, t ≤ n. Są to numery placówek początkowej i docelowej.

출력 형식

W pierwszym wierszu powinna zostać wypisana jedna dodatnia liczba całkowita r - liczba różnych par (koszt, czas) charakteryzujących wszystkie trasy transportu przesyłek z placówki s do t, od których nie ma lepszych. W kolejnych r wierszach powinny być wypisane te pary, w kolejności rosnących kosztów. Każda para powinna być wypisana w osobnym wierszu, a koszt i czas powinny być oddzielone pojedynczym odstępem.

예제 입력

9 9
C 1 2
C 2 1
A 20 30
B 12 13
C 1 1
A 23 27
B 10 15
C 1 3
C 3 2
1 4 1 1
2 4 1 2
3 4 3 2
5 3 2 7
3 6 5 1
6 4 4 3
6 7 4 4
7 8 3 3
7 9 2 2
1 2

예제 출력

2
55 66
60 65