Customs duties-3#1728
Recently, the queen of AlgoLand invented a new way of collecting money for her royal court. She decided that every resident who wishes to travel from one city to another must pay for this wish with their own money.
AlgoLand contains cities, numbered from to . Some cities are connected by roads, each allowing movement in both directions. Once a traveler starts moving along a road, they must travel it to the end.
Suppose now that a resident wishes to travel from city to city . The queen's new decree states that while traveling along any road during this journey, the police may collect a customs fee from the traveler for the benefit of the royal court (or might not collect it). If the traveler does not have enough money to pay the fee at any collection, they are immediately sent to prison. The decree also sets the exact fee for each road. Since the queen cares about her residents, she forbade the police from collecting a customs fee more than three times during a single journey.
Note that if there are several ways to get from to , the traveler can freely choose any route.
Write a program that:
reads from the input file a description of the cities and roads in the country, as well as the numbers of the starting and ending cities for the journey;
determines the minimum amount of money a resident must take to be guaranteed not to go to jail during the journey;
and writes the result to the output file.
The first line contains the numbers and (2 \le N \le 10000, 1 \le M \le 100000), separated by a space — the number of cities and roads. The following lines describe the roads. Each line contains three numbers , , (1 \le X, Y \le N; X \ne Y; 1 \le Z \le 1000000000) separated by spaces, meaning there is a road between cities and , and the fee for its passage is currency units. The last line contains the numbers and (1 \le A, B \le N; A \ne B) — the numbers of the starting and ending cities of the journey. It is guaranteed that there is at least one way to travel from to .
The only line of the output file should contain a single number: the minimum amount of money a resident must take to travel from city to city and be sure not to go to jail, regardless of the actions of the police.
Пример 1