Условие

---

Задача I. Множества
---
Даден е граф с N, 2 ≤ N ≤ 10 000 върха, номерирани с числата от 1 до N. Върховете са разделени в две множества А и В и са свързани с M двупосочни ребра. Преминаването през ребро става за определено време, което ви е известно – цяло положително число, не по-голямо от 1 000. Напишете програма, която за всеки връх от множеството А определя минималното време, необходимо за придвижване от него до някой връх от множеството В.

Вход
---
На първия ред на стандартния вход ще бъде зададен броят на тестовете. Всеки тест започва с ред, съдържащ броя на върховете N. Следва ред с N символа 'А' или 'В', определящи принадлежността на поредния връх към съответното множество. Следва ред с броя на ребрата М. На следващите M реда са зададени номерата на два върха и времето за преминаване между тях по това ребро.

Изход
---
За всеки пример извеждайте на стандартния изход толкова реда, колкото са върховете от множеството А. На всеки от тези редове трябва да има по две числа – номер на връх от множеството А и минималното време, за придвижване от него до някой връх от множеството В или -1, ако такъв връх не съществува. Върховете трябва да са подредени в нарастващ ред на номерата им.

Примерен вход 
---
1
8
BABABAAB
10
1 6 10
2 3 21
2 4 2
2 6 7
4 7 7
4 5 18
6 8 3
6 7 6
8 7 10
7 3 11

Примерен изход
---
2 10
4 12
6 3
7 9