|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||256 MB||6||3||3||75.000%|
In some country there is a huge oil transportation system. The system consists of control stations. Some pairs of stations are conneted by pipes.
System is conneted, so there is a path via pipes from each control station to each other control station. But there are some pipes such that if they will broke, the system will become not conneted. These pipes are called magistral. It's guaranteed that there is at least one magistral pipe.
The company has bought two robots for maintaining magistral pipes. After receiving a command, some magistral pipe will be chosen and both robots start to move to different ends of this pipe. Arrival time is the time needed for robot that will arrive to its destination later.
Robots are moving along pipes. They pass one unit of length in one unit of time. At the moment of receiving the command robots are located on the given control stations (may be different).
Write a program that will determine a magistral pipe such that robots' arrival time is minimal possible.
First line of the input contains two integer numbers N (2 ≤ N ≤ 100 000) and M (2 ≤ M ≤ 100 000) - number of control stations and pipes.
Each of the next M lines contains three integers: numbers of two control stations and length of the pipe conneting them. Length of the pipe does not exeed 1000.
(M + 2)-th line contains two integers: numbers of the control stations where robots are located at the moment of receiving command.
Output the only one number - minimal time robots' arrival time to a magistral pipe.
8 11 1 2 3 1 3 5 1 4 8 3 4 4 2 4 3 4 5 2 5 6 9 5 7 3 6 7 4 6 8 5 7 8 6 3 6