题目描述

给定一个无向图。这个图除了顶层结点外，还可以包含若干个自己的缩小副本；每个副本内部又会包含同样数量的副本，如此无限递归下去，因此整个图具有无限多个结点。

顶层结点使用 A～J 表示。一个图副本最多包含 $9$ 个直接子副本，编号为 1～9。例如 C2 表示“当前图的第 $2$ 个子副本中的结点 C”。

当向下进入一层递归副本时，原图中所有边的权值都会变为上一层的一半并向下取整。也就是说，如果某条顶层边的权值为 $w$，那么它在深度 $k$ 的副本中的权值为 $\left\lfloor w/2^k\right\rfloor$。由于边权有限，当递归足够深后，所有边权都会变为 $0$。

下面的示意图展示了一类递归图结构：

每条输入边由两个结点标识和一个权值组成。结点标识可以是单独一个大写字母，如 A，表示当前层的顶层结点；也可以是大写字母后跟一个数字，如 C3，表示当前层第 $3$ 个子副本中的结点 C。

不会出现直接连接同一个子副本内两个结点的边，例如 A3 B3 10 不合法；但允许连接不同子副本，例如 A4 B5 20。

给定起点和终点，它们都是顶层结点。求无限递归图中两点之间的最短路长度。如果不存在路径，或者最短路长度大于 $10^9$，输出 -1。

输入格式

第一行输入：

m start end

其中 $m$ 表示边的数量，start、end 分别为起点和终点的大写字母。

接下来 $m$ 行，每行输入：

u v w

表示结点标识 u 与 v 之间存在一条无向边，顶层权值为 $w$。

输出格式

输出一个整数，表示从 start 到 end 的最短路长度。

如果不存在路径，或者最短路长度大于 $10^9$，输出 -1。

样例 1

输入

5 A B
A B 20
C D 13
A C1 1
D1 C2 2
D2 B 3

输出

18

样例 2

输入

5 A B
A B 800
A C1 4
D1 B 4
C A2 4
B2 D 4

输出

14

样例 3

输入

2 A B
A A1 1
B B1 1

输出

-1

数据范围

• $1\le m\le50$；
• 顶层结点只会使用 A～J；
• 子副本编号只会使用 1～9；
• $0\le w\le1000$；
• 不会有两条边连接完全相同的一对结点；
• 不会出现连接同一个子副本内部两个结点的输入边；
• start 和 end 都会在输入边中出现。