题目描述

在一款网络游戏中，玩家可以收集不同类型的能量卡牌。每张能量卡牌能让玩家获得一种独特的游戏法术。游戏中总共有 $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$（$0 < P_o \le m$）和目标卡牌 $P_t$（$0 < P_t \le m$）。同时，$P_o$ 和 $P_t$ 不能相同。第三部分包含一系列三元组，每个三元组包含两个卡牌编号 $i$、$j$ 以及这两种能量卡牌 $(P_i, P_j)$ 之间的交易费用 $c_{i,j}$（$0 < c_{i,j} \le 20$）。第三部分以一个单独的 $0$ 结束。

输出格式

对于每个测试用例，输出完成交易所需的最少游戏点数。

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

4
4

提示

翻译由 DeepSeek V4 Pro 完成