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.

ThereisAlgoLandN cities, numbered from1 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 townAto townB.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 fromcityA tocityB, 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.


The first linecontains the numbersN and M (2N10000, 1M100000), separated by a space-the number of citiesand roads.The followingM linesdescribethe road.Each linedescribes onewayandcontains three numbersX, Y, Z (1X, YN; XY; 1Z1000000000) separated by spaces, meaning that theroad connects thetownof X and Yandthe fee foritspassageis Zcurrency units.The last line containsthe number ofA and B (1A, BN; AB) - numberof initial and finalurbantravel.It is guaranteed thatthere exists at leastone way totravel fromA to B.


The onlyline of output fileshould containanumber equal tothe minimum amountof money thatshouldtake aresidentto be ableto travelfrom cityA tocityB, andthusguaranteed not togo to jailregardless of what thepolice officers.

Time limit 1 second
Memory limit 64 MiB
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
Author Ivan Metelsky