eolymp
bolt
Try our new interface for solving problems
Problems

Customs duties-3

Customs duties-3

Time limit 1 second
Memory limit 64 MiB

Recently, the queen of country AlgoLand invented a new way of laundering money for his royal court. She decided that every citizen who wishes to travel from one city to another country, should pay for this wish with their money.

There is AlgoLand N cities, numbered from 1 to N. Some cities are connected by roads, traffic which is allowed in both directions. Since traffic on any road, the traveler must get to the end.

Suppose now that a resident of the country wants to make a trip out of town A to town B. The new decree of Queen says that when driving on any road of the country during this trip, the police can take from this resident of customs duties in favor of the royal court (or may not take). If this resident have enough money to pay a fee, it automatically goes to prison. The decree also sets the amount of fees for each road of the country. Since the Queen is concerned about the inhabitants of the country, it forbade the police to take a tax resident for more than three times during one trip.

Note that if there are several ways to get from city A to city B, then the resident can choose to travel any one of them on their own.

Write a program that:

  • enters from the input file description of towns and roads in the country, as well as the number of initial and final trip of the city;

  • determines what the minimum amount of money should take a resident to not guaranteed to be imprisoned during the trip;

and outputs the result to an output file.

Input data

The first line contains the numbers N and M (2N10000, 1M100000), separated by a space - the number of cities and roads. The following M lines describe the road. Each line describes one way and contains three numbers X, Y, Z (1X, YN; XY; 1Z1000000000) separated by spaces, meaning that the road connects the town of X and Y and the fee for its passage is Z currency units. The last line contains the number of A and B (1A, BN; AB) - number of initial and final urban travel. It is guaranteed that there exists at least one way to travel from A to B.

Output data

The only line of output file should contain a number equal to the minimum amount of money that should take a resident to be able to travel from city A to city B, and thus guaranteed not to go to jail regardless of what the police officers.

Examples

Input example #1
5 6
1 2 10
1 3 4
3 2 3
1 4 1
4 5 2
5 2 3
1 2
Output example #1
6
Author Ivan Metelsky