Robots and Oil Transportation System#250
In some country, there is a huge oil transportation system. This system consists of many control stations, some pairs of which are connected by pipes.
Initially, the system is connected, so there is a path by pipes between any two control stations. However, there are some pipes such that removing any of them would make the system disconnected. Such pipes are called magistral pipes. It is guaranteed that there is at least one magistral pipe.
The company has bought two robots to maintain the magistral pipes. When a command is received, some magistral pipe is chosen, and both robots start moving towards different ends of this pipe. The arrival time is the time taken by the robot who arrives at its destination later.
Robots move along the pipes and travel a unit distance in a unit of time. At the moment the command is given, the robots are located at specified control stations (possibly different).
Write a program to determine the magistral pipe for which the robots' arrival time is minimal.
The first line contains two integers (2 \leq N \leq 100000) and (2 \leq M \leq 100000) — the number of control stations and pipes, respectively.
Each of the next lines contains three integers: the numbers of two control stations and the length of the pipe connecting them. The length of a pipe does not exceed .
The (M+2)-th line contains two integers: the numbers of the control stations where the robots are located at the time of the command.
Print a single integer — the minimal time in which the robots can arrive at a magistral pipe.
Example 1