Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

B. Строковая задача
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Мальчик Валера очень любит строки. А еще больше он любит, когда строки одинаковые. Поэтому на досуге Валера сам с собой играет в следующую игру. Он берет две произвольные строки, состоящие из строчных букв латинского алфавита, и пытается сделать из них две равные друг другу. По правилам его игры, во время очередного хода Валере разрешается заменить в одной из строк один произвольный символ Ai на произвольный символ Bi, но при этом за каждый свой ход ему придется заплатить некоторую сумму денег, равную Wi. Ходов разрешается сделать бесконечно много. Поскольку Валера очень экономный мальчик и никогда не тратит свои деньги зря, он попросил Вас, как опытного программиста, помочь ему ответить на вопрос: какое наименьшее количество денег должно быть у Валеры, чтобы он смог получить одинаковые строки.

Входные данные

В первых двух строках входного файла заданы две исходные непустые строки s и t, состоящих из строчных латинских букв. Длины обеих строк не превосходят 105. В следующей строке задано целое число n (0 ≤ n ≤ 500) — количество возможных замен. В следующих n строках заданы два символа Ai и Bi, являющихся строчными латинскими буквами, а также целое число Wi (0 ≤ Wi ≤ 100), означающие, что разрешено заменить символ Ai на символ Bi в любой из строк, потратив количество денег в размере Wi.

Выходные данные

Если решение существует, выведите в выходной файл ответ на задачу, а также получившуюся строку. В противном случае в единственной строке выведете -1. Если оптимальных решений несколько, выведите любое из них.

Примеры
Входные данные
uayd
uxxd
3
a x 8
x y 13
d c 3
Выходные данные
21
uxyd
Входные данные
a
b
3
a b 2
a b 3
b a 5
Выходные данные
2
b
Входные данные
abc
ab
6
a b 4
a b 7
b a 8
c b 11
c a 3
a c 0
Выходные данные
-1