# Customs duties-3

# Customs duties-3

Recently,the queen ofcountryAlgoLandinventeda new way oflaunderingmoneyforhisroyal court.She decided thateverycitizenwho wishesto travelfrom one cityto anothercountry,shouldpay forthis wishwith their money.

ThereisAlgoLand**N** cities, numbered from**1** to **N**.Somecities are connectedby roads,trafficwhichis allowedin both directions.Sincetraffic onanyroad, the travelermustget tothe end.

Suppose nowthat a resident ofthe countrywantsto make a tripout of town**A**to town**B**.The new decreeof Queensays thatwhen drivingonany roadof the countryduringthis trip, the policecantakefrom thisresident ofcustoms dutiesin favor ofthe royal court(or maynottake).If thisresidenthaveenough money topay a fee, it automaticallygoes to prison.The decree alsosets the amount offeesforeach roadof the country.Sincethe Queenis concernedabout the inhabitantsof the country, itforbadethe policeto takeataxresidentfor more thanthree timesduring onetrip.

Note that ifthere are several waysto get fromcity**A** tocity**B**, then theresident canchoosetotravelany one of themon their own.

Write a program that:

- entersfrom the input filedescriptionof towns androads in the country,as well as thenumberof initial and finaltripof the city;
- determines whatthe minimum amountof moneyshouldtake aresidenttonotguaranteedto be imprisonedduring the trip;

and outputs theresult to an outputfile.

**Input**

The first linecontains the numbers**N** and **M** (**2** ≤ **N** ≤ **10000**, **1** ≤ **M** ≤ **100000**), separated by a space-the number of citiesand roads.The followingM linesdescribethe road.Each linedescribes onewayandcontains three numbers**X**, **Y**, **Z** (**1** ≤ **X**, **Y** ≤ **N**; **X** ≠ **Y**; **1** ≤ **Z** ≤ **1000000000**) separated by spaces, meaning that theroad connects thetownof **X** and **Y**andthe fee foritspassageis **Z**currency units.The last line containsthe number of**A** and **B** (**1** ≤ **A**, **B** ≤ **N**; **A** ≠ **B**) - numberof initial and finalurbantravel.It is guaranteed thatthere exists at leastone way totravel from**A** to **B**.

**Output**

The onlyline of output fileshould containanumber equal tothe minimum amountof money thatshouldtake aresidentto be ableto travelfrom city**A** tocity**B**, andthusguaranteed not togo to jailregardless of what thepolice officers.

5 6 1 2 10 1 3 4 3 2 3 1 4 1 4 5 2 5 2 3 1 2

6