Problem Description

In an online game, a player can collect different types of power cards. Each power card can enable a player to have a unique game magic. There are $m$ power cards available in the game as $(P_1, \dots, P_m)$. A power card can be acquired by game points or through trading with others. In order to support trading easier, a platform has been built. The platform charges a fixed amount $C_{i,j}$ game points for trading respective power cards $P_i$ and $P_j$. Note: Trading $P_i$ to $P_j$ or $P_j$ to $P_i$ would be of the same charge.

Write a program to calculate the minimal number of game points with a given original power card ($P_o$) to a target one ($P_t$). The output of your program should be the minimal game point value.

Input Format

The test data may contain many test cases. Each test case contains three data sections. The first section is an integer to indicate the number of power card types $m$ ($1 < m \le 50$). The second section contains two integers representing the original power card $P_o$ ($0 < P_o \le m$) and the target power card $P_t$ ($0 < P_t \le m$). Also, $P_o$ cannot be the same as $P_t$. The third section has a set of triplets and each triplet contains two cards id $i$, $j$ and the charge amount $c_{i,j}$ ($0 < c_{i,j} \le 20$) between $2$ types of power cards $(P_i, P_j)$. The end part of section $3$ contains a single $0$.

Output Format

The output for each test case is the minimal number of game points needed for the trading.

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