CF33B.String Problem

Boy Valera likes strings. And even more he likes them, when they are identical. That's why in his spare time Valera plays the following game. He takes any two strings, consisting of lower case Latin letters, and tries to make them identical. According to the game rules, with each move Valera can change one arbitrary character A__i in one of the strings into arbitrary character B__i, but he has to pay for every move a particular sum of money, equal to W__i. He is allowed to make as many moves as he needs. Since Valera is a very economical boy and never wastes his money, he asked you, an experienced programmer, to help him answer the question: what minimum amount of money should Valera have to get identical strings.

男孩瓦列拉喜欢字符串，尤其喜欢两个完全相同的字符串。因此，在空闲时间里，瓦列拉会玩这样一个游戏：他任取两个仅由小写拉丁字母组成的字符串，并尝试使它们变得完全相同。根据游戏规则，每次操作中，瓦列拉可以将其中一个字符串中的任意一个字符 $A_i$ 修改为任意另一个字符 $B_i$，但每次操作需支付一笔特定的费用，金额为 $W_i$。他可以进行任意多次操作。由于瓦列拉是个非常节俭的男孩，从不浪费金钱，他请你这位经验丰富的程序员帮忙回答一个问题：瓦列拉至少需要准备多少钱，才能使这两个字符串变得完全相同？

The first input line contains two initial non-empty strings s and t, consisting of lower case Latin letters. The length of each string doesn't exceed 105. The following line contains integer n (0 ≤ n ≤ 500) — amount of possible changings. Then follow n lines, each containing characters A__i and B__i (lower case Latin letters) and integer W__i (0 ≤ W__i ≤ 100), saying that it's allowed to change character A__i into character B__i in any of the strings and spend sum of money W__i.

第一行输入包含两个初始的非空字符串 $s$ 和 $t$，均由小写拉丁字母组成。每个字符串的长度不超过 $10^5$。接下来一行包含一个整数 $n$（$0 \leq n \leq 500$），表示允许的字符变换种类数。随后是 $n$ 行，每行包含字符 $A_i$ 和 $B_i$（均为小写拉丁字母）以及一个整数 $W_i$（$0 \leq W_i \leq 100$），表示允许在任一字符串中将字符 $A_i$ 变换为字符 $B_i$，花费金额为 $W_i$。

If the answer exists, output the answer to the problem, and the resulting string. Otherwise output -1 in the only line. If the answer is not unique, output any.

如果答案存在，输出该问题的答案以及对应的结果字符串；否则，在唯一的一行中输出 $-1$。如果答案不唯一，输出任意一个即可。