SHEEPNAM - Nam The Sheep Watcher

It's Friday afternoon. Nam and Ryan decided to go on a bike ride on the Darebin Creek Trail. The trail can be described as a tree with n nodes A1, A2 … An representing the crossroads. There are n-1 roads connecting the nodes, and the time it takes to ride from node Ai to node Bi (or from Bi to Ai, you can go either way) is Ti (1 ≤ Ai, Bi ≤ n, 1 ≤ i ≤ n-1, 1 ≤ Ti ≤ 10^9).

Nam and Ryan start the trip from Uni, which is at node X. Because Nam has never seen a sheep, Ryan decided to take Nam to a field nearby at node Y where, for some reason, there is a lot of sheep. 

Riding bikes and seeing sheep are fun and all, but Nam also needs to go home by 7 pm to play his favorite game, Doki Doki Literature Club. Therefore, Nam wants to know how long it will take to get to the sheep.

Requirement

Calculate the time it takes for Nam and Ryan to travel from Uni (node X) to the sheep field (node Y).

Input

- The first line contain three integer n, X, Y (n <= 10^5, 1 <= X, Y <= n)

- The following n-1 lines, each contains 3 integers Ai, Bi, and Ti (1 <= Ai, Bi <= n, 1 <= i <= m, 1 <= Ti <= 10^9).

Output

A single integer which is the answer.

Example

Input:
6 2 6
1 2 2
2 3 1
2 4 5
4 6 2
4 5 4

Output:
7

Added by:LTU ComSoc
Date:2022-04-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.