ADA University - February 3 - Dijkstra
The word of sponsor
At the end of the tournament "The New-Year Night", the sponsor decided to send the presents to m prize-winners by post. You know the number of competitors n and the delivering time for post between some departments of "Ukrpost". Find the time when the last prize-winner will receive his prize.
In the first line we have 3 integers: the number of tournament competitors n, the number of prizes from sponsor m and the number of known delivering time k for post between some departments. In next line we have the number of competitors, who became prize-winners. These numbers are separated with a space.
Each of the next k lines contains 3 numbers and describe the information about known delivering time for post between some departments in format: a b t where a and b are numbers of departments, t (0 ≤ t ≤ 365) is time of delivering for post between some departments.
The last line gives the post department number, where from the sponsor will send his presents. It is known that 1 ≤ n, m, a, b ≤ 365.
If all presents will be deliver to competitors than make clear in first line "**The good sponsor!**", and in next line male clear through what time the least of prize-winners will receive his prize. If one of competitors can’t receive his prize than you must make clear in one line "**It is not fault of sponsor...**". The phrases make clear without quotation marks.
3 2 2 2 3 1 2 3 2 3 4 1
The good sponsor! 7