Московская олимпиада по информатике

на сайте www.olympiads.ru

Московская городская олимпиада школьников по информатике, 2005/06 учебный год
при поддержке компании

Задача I. Олимпиада по алхимии

В государстве алхимиков есть N населённых пунктов, пронумерованных числами от 1 до N, и M дорог. Населённые пункты бывают двух типов: деревни и города. Кроме того, в государстве есть одна столица (она может располагаться как в городе, так и в деревне). Каждая дорога соединяет два населённых пункта, и для проезда по ней требуется T_i минут. В столице было решено провести 1-ю государственную командную олимпиаду по алхимии. Для этого во все города из столицы были отправлены гонцы (по одному гонцу на город) с информацией про олимпиаду.

Напишите программу, которая посчитает, в каком порядке и через какое время каждый из гонцов доберётся до своего города. Считается, что гонец во время пути не спит и нигде не задерживается.

Формат входных данных

Во входном файле сначала записаны 3 числа N, M, K - количество населенных пунктов, количество дорог и количество городов (2≤N≤1000, 1≤M≤10000, 1≤K≤N). Далее записан номер столицы C (1≤C≤N). Следующие K чисел задают номера городов. Далее следуют M троек чисел S_i, E_i, T_i, описывающих дороги: S_i и E_i - номера населенных пунктов, которые соединяет данная дорога, а T_i - время для проезда по ней (1≤T_i≤100).

Гарантируется, что до каждого города из столицы можно добраться по дорогам (возможно, через другие населенные пункты).

Формат выходных данных

Выведите в выходной файл K пар чисел: для каждого города долен быть выведен его номер и минимальное время, когда гонец может в нем оказаться (время измеряется в минутах с того момента, как гонцы выехали из столицы). Пары в выходном файле должны быть упорядочены по времени прибытия гонца.

Примеры

5 4 5 1
1 2 3 4 5
1 2 1
2 3 10
3 4 100
4 5 100

1 0
2 1
3 11
4 111
5 211

5 5 3 1
2 4 5
2 1 1
2 3 10
3 4 100
4 5 100
1 5 1

5 1
2 1
4 101