Customs duties-2#1727
Recently, the queen of the country AlgoLand invented a new way of laundering money for her royal court. She decided that every citizen who wishes to travel from one city to another must pay for this wish with their money.
There are cities in AlgoLand, numbered from to . Some cities are connected by roads, with traffic allowed in both directions. While traveling on any road, the traveler must get to its end.
Suppose now that a resident of the country wants to make a trip from city to city . The new decree of the Queen says that when driving on any road of the country during this trip, the police can take customs duties from the resident in favor of the royal court (or may not take any). If this resident does not have enough money to pay a fee, they automatically go 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, she forbade the police from taking a tax from a resident more than two times during one trip.
Note that if there are several ways to get from city to city , the resident can choose to travel any one of them on their own.
Write a program that:
reads from the input file the description of towns and roads in the country, as well as the cities of initial and final trip;
determines the minimum amount of money a resident should take to be guaranteed not to be imprisoned during the trip;
and outputs the result to an output file.
The first line contains the numbers and (2 \leq N \leq 10000, 1 \leq M \leq 100000), separated by a space — the number of cities and the number of roads. The following lines describe the roads. Each line describes one road and contains three numbers , , (1 \leq X, Y \leq N; X \neq Y; 1 \leq Z \leq 1000000000), separated by spaces, meaning that the road connects towns and , and the fee for its passage is currency units. The last line contains the numbers and (1 \leq A, B \leq N; A \neq B) — the numbers of initial and final cities of the travel. It is guaranteed that there exists at least one way to travel from to .
The only line of the output file should contain a number equal to the minimum amount of money that a resident should take to be able to travel from city to city , and thus be guaranteed not to go to jail regardless of what the police officers do.
Example 1