Customs duties-1#1726
Recently, the queen of AlgoLand has invented a new way for her royal court to collect money. She decided that every citizen who wishes to travel from one city to another must pay for this journey out of their own funds.
AlgoLand has cities, numbered from to . Some cities are connected by roads, each of which can be traveled in both directions. Once a traveler enters a road, they must go to its end.
Suppose that a resident wishes to travel from city to city . According to the queen's new decree, when passing along any road during this trip, the police may collect (or may not collect) a customs fee from the resident in favor of the royal court. If the resident does not have enough money to pay the fee, they are automatically sent to prison. The decree also sets the amount of the fee for each road. Since the queen is concerned about her citizens, she has forbidden the police to collect the fee from a resident more than once during a single trip.
Note that if there are several ways to travel from city to city , the resident can choose any route.
Write a program that:
Reads the description of the cities and roads, as well as the numbers of the starting and ending cities for the trip;
Determines the minimum amount of money a resident must take to guarantee that they will not be sent to prison during the trip;
Outputs the result.
The first line contains two integers and (2 \leq n \leq 10000, 1 \leq m \leq 100000) — the number of cities and roads, respectively. The next lines describe the roads. Each of these lines contains three integers , , (1 \leq x, y \leq n, x \ne y, 1 \leq z \leq 10^9), indicating that there is a road connecting cities and , and the fee for traveling on this road is currency units. The last line contains two integers and (1 \leq A, B \leq n, A \ne B) — the numbers of the starting and ending cities. It is guaranteed that there is at least one route from to .
Print the minimum amount of money that a resident must take to be able to travel from city to city and, regardless of police actions, be guaranteed not to go to prison.
Example 1