e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Robots and Oil Transportation Sy

Robots and Oil Transportation Sy

In some country there is a huge oil transportation system. The system consists of control stations. Some pairs of stations are connected by pipes.

prb250

System is connected, 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 connected. 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.

Input

First line of the input file contains two integer numbers N (2 <= N <= 100000) and M (2 <= M <= 100000) - 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 connecting them. Length of the pipe does not exceed 1000.

(M+2)-th line contains two integers: numbers of the control stations where robots are located at the moment of receiving command.

Output

Output the only one number - minimal time robots' arrival time to a magistral pipe.

Time limit 2 seconds
Memory limit 64 MiB
Input example #1
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
Output example #1
7