男孩瓦莱拉喜欢弦乐。当它们完全相同时,他更喜欢它们。这就是为什么瓦莱拉在业余时间玩下面的游戏。他取任意两个由小写拉丁字母组成的字符串,并尝试使它们相同。根据游戏规则,瓦莱拉每走一步都可以将其中一个字符串中的任意一个字符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