在某款网络游戏中，玩家可以收集不同类型的能力卡。每张能力卡都能让玩家获得一种独特的游戏魔法。游戏中共有 $m$ 种能力卡，记为 $(P_1, \dots, P_m)$。能力卡可以通过游戏点数获取，也可以通过与其他玩家交易获得。为了方便交易，平台建立了一个交易系统。平台对交易相应的能力卡 $P_i$ 和 $P_j$ 收取固定数量的 $C_{i,j}$ 游戏点数。注意：将 $P_i$ 交易为 $P_j$ 或将 $P_j$ 交易为 $P_i$ 所需的费用相同。

编写一个程序，计算给定初始能力卡 $P_o$ 到目标能力卡 $P_t$ 所需的最少游戏点数。程序的输出应为最少游戏点数值。

输入格式

测试数据可能包含多个测试用例。每个测试用例包含三个数据部分。第一部分是一个整数，表示能力卡的类型数量，记为 $m$ ($1 < m \le 50$)。第二部分包含两个整数，分别表示初始能力卡 $P_o$ 的类型 $o$ ($0 < o \le m$) 和目标能力卡 $P_t$ 的类型 $t$ ($0 < t \le m$)。此外，$o$ 不等于 $t$。第三部分包含一组三元组，每个三元组包含两个卡片类型 $i, j$ 以及两种能力卡 $(P_i, P_j)$ 之间的交易费用 $c_{i,j}$ ($0 < c_{i,j} \le 20$)。第三部分的结尾包含一个单独的 $0$。

输出格式

对于每个测试用例，输出将初始能力卡 $P_o$ 交易为目标能力卡 $P_t$ 所需的最少游戏点数。

样例

输入 1

5
2 4
1 2 1
2 3 4
5 4 2
3 4 1
2 5 2
0
7
6 7
1 2 4
1 3 2
1 6 1
2 7 1
3 4 2
4 7 1
4 5 1
5 6 2
0

输出 1

4
4