Two Robots

A new cave was discovered in Gangwon Province in 2018. This cave contains a total of N wide rooms connected to each other by narrow passages. The N rooms are numbered 1 through N and are called room 1, room 2, …, room N. Exactly N-1 passages were found; each connects two different rooms, and no passage meets another passage partway along. Using these passages, one can travel between any two rooms, and for any two rooms the path that does not traverse the same passage more than once is unique.

To investigate the newly discovered cave, two cave exploration robots will be used. At some point the two robots must communicate to share the information each has gathered. To communicate, the two robots must be located on the same passage inside the cave. Note that the two rooms at the ends of any passage are also considered to be on that passage.

\

Given information about the passages in the cave and the current positions of the two robots, write a program that computes the minimum total distance the robots must travel to communicate with each other.

Each passage of the cave is given by the numbers of the two rooms at its ends and its length. The positions of the two robots are given as room numbers.

The first line of standard input contains the number of rooms in the cave N and the room numbers where the two robots are located, as three positive integers separated by spaces. Then the N-1 passages of the cave are given one per line. Each passage is given on one line as three positive integers separated by spaces; the first two integers are the numbers of the rooms at the ends of the passage, and the third integer is the length of that passage.

Print to standard output, as an integer, the minimum total distance the two robots must travel from their current positions to communicate with each other.

In every subtask, 1 ≤ N ≤ 100,000, and the length of a passage does not exceed 1,000.