Piglet plans to visit Winnie-the-Pooh in the morning and return home in the evening. As is well known, Piglet and Winnie-the-Pooh live in a forest inhabited by heffalumps. Piglet is very afraid of heffalumps and has long since drawn a map of the forest, marking the clearings and the paths connecting them, indicating the danger level for each path, specifically, how many times a heffalump has been seen on it. "The more often a heffalump is seen on a path, the more dangerous it is," Piglet reasonably believed. Piglet also rightly considered that if he runs along a path in the morning, he should not run along it in the evening, because the heffalumps will already know that Piglet runs on that path and might attack him. Thus, Piglet wants to find a path home such that he does not run along the same paths he used in the morning.

Using Piglet's map, help him determine the minimum total danger of the path from Piglet's house to Winnie-the-Pooh's house and back, without traversing any path more than once.

Input

The first line contains four positive integers separated by spaces: $N$ — the number of clearings, $M$ — the number of paths, and $A$ and $B$ — the numbers of the clearings where Piglet's house and Winnie-the-Pooh's house are located, respectively, $2 \le N \le 300$, $1 \le M \le N \cdot (N - 1)/2$, $1 \le A, B \le N$, $A \neq B$.

The next $M$ lines, each containing three non-negative integers $V_i, W_i, D_i$ separated by spaces, each describe one path: $V_i$ and $W_i$ are the numbers of the clearings connected by the $i$-th path, and $D_i$ is the danger of this path, $1 \le V_i, W_i \le N$, $V_i \neq W_i$, $1 \le D_i \le 100$.

Any two clearings are connected by at most one path.

Output

The first and only line should contain one integer — the minimum possible total danger of the path from the clearing with Piglet's house to the clearing with Winnie-the-Pooh's house and back, without traversing any path more than once. If no such path exists, output $-1$.

Examples

Input 1

4 5 1 4
1 2 1
2 4 2
1 3 4
3 4 3
1 4 6

Output 1

9