← 返回题目列表

Codeforces · 33/B

B. 字符串问题

中文机器翻译题面 查看原题

男孩瓦莱拉喜欢弦乐。当它们完全相同时,他更喜欢它们。这就是为什么瓦莱拉在业余时间玩下面的游戏。他取任意两个由小写拉丁字母组成的字符串,并尝试使它们相同。根据游戏规则,瓦莱拉每走一步都可以将其中一个字符串中的任意一个字符Ai变成任意字符Bi,但他必须为每一步支付一定的金钱,等于Wi。他可以根据需要进行尽可能多的动作。由于 Valera 是一个非常节约的男孩,从不浪费钱,所以他请你,一位经验丰富的程序员,帮他回答这个问题:Valera 最少需要多少钱才能得到相同的字符串。

输入

第一个输入行包含两个初始非空字符串 s 和 t,由小写拉丁字母组成。每个字符串的长度不超过 105。以下行包含整数 n (0 ≤ n ≤ 500) - 可能更改的数量。接下来n行,每行包含字符Ai和Bi(小写拉丁字母)和整数Wi(0≤Wi≤100),表示可以将任意字符串中的字符Ai变为字符Bi,并花费金额Wi。

输出

如果答案存在,则输出问题的答案以及结果字符串。否则在唯一的一行中输出-1。如果答案不唯一,则输出任意一个。

示例

输入 #1

uayd
uxxd
3
a x 8
x y 13
d c 3

输出 #1

21
uxyd

输入 #2

a
b
3
a b 2
a b 3
b a 5

输出 #2

2
b

输入 #3

abc
ab
6
a b 4
a b 7
b a 8
c b 11
c a 3
a c 0

输出 #3

-1