e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dijkstra algorithm

Слово спонсора

По завершенню турніру "Новорічна ніч" спонсор вирішив відправити m призерам подарунки поштою. Знаючи кількість учасників n та час доставки пошти між деякими відділеннями "Укрпошти", знайти, через який час останній з призерів отримає свій приз.

Вхідні дані

Перший рядок містить 3 числа: кількість учасників турніру n, кількість призів спонсора m та кількість відомих часових термінів доставки між деякими з відділень k. У наступному рядку через пропуск вказані номери учасників, що стали призерами.

Далі йде k рядків по 3 числа у рядку з інформацією про відомі часові терміни доставки між деякими з відділень у форматі: a b t, де a та b - номери відділень, t (0t365) - час доставки пошти між ними. У останньому рядку єдине число - номер поштового відділення, з якого спонсор відправлятиме подарунки. Відомо, що 1n, m, a, b365.

Вихідні дані

Якщо всі призи будуть доставлені учасникам вивести у першому рядку "The good sponsor!", а у наступному час, через який останній з призерів отримає свій приз. Якщо хоча б один з учасників не зможе отримати приз - вивести у єдиному рядку "It is not fault of sponsor...". Фрази виводити без лапок.

prb34.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 2 2
2 3
1 2 3
2 3 4
1
Вихідні дані #1
The good sponsor!
7