题目描述

小男孩 Valera 喜欢字符串。当它们是相同的时候，他会更喜欢它们。这就是为什么 Valera 会在空闲时间玩下面这个游戏。

他有两个由小写字母组成的字符串，根据游戏规则，Valera 每次可以将其中一个字符串中的任何一个字母 $A_i$ 变为 $B_i$，但要支付 $W_i$ 的代价。请你输出让两个字符串相同的最小代价，无解输出 $-1$。

输入格式

第 $1,2$ 行两个字符串。

第 $3$ 行一个整数 $n$，表示可能的变化的个数。

接下来 $n$ 行，每行两个字符一个整数分别表示 $A_i$，$B_i$，与 $W_i$。

输出格式

无解输出 $-1$。

有解一共 $2$ 行，第 $1$ 行一个整数表示最小代价；第 $2$ 行一个字符串表示最后相同的串。

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