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