В государстве алхимиков есть N населённых пунктов, пронумерованных числами от 1 до N, и M дорог. Населённые пункты бывают двух типов: деревни и города. Кроме того, в государстве есть одна столица (она может располагаться как в городе, так и в деревне). Каждая дорога соединяет два населённых пункта, и для проезда по ней требуется Ti минут. В столице было решено провести 1-ю государственную командную олимпиаду по алхимии. Для этого во все города из столицы были отправлены гонцы (по одному гонцу на город) с информацией про олимпиаду.
Напишите программу, которая посчитает, в каком порядке и через какое время каждый из гонцов доберётся до своего города. Считается, что гонец во время пути не спит и нигде не задерживается.
Входные данные
Во входном файле сначала записаны 3 числа N, M, K — количество населенных пунктов, количество дорог и количество городов (2?N?1000, 1?M?10000, 1?K?N). Далее записан номер столицы C (1?C?N). Следующие K чисел задают номера городов. Далее следуют M троек чисел Si, Ei, Ti, описывающих дороги: Si и Ei — номера населенных пунктов, которые соединяет данная дорога, а Ti — время для проезда по ней (1?Ti?100).
Гарантируется, что до каждого города из столицы можно добраться по дорогам (возможно, через другие населенные пункты).
Выходные данные
Выведите в выходной файл K пар чисел: для каждого города должен быть выведен его номер и минимальное время, когда гонец может в нем оказаться (время измеряется в минутах с того момента, как гонцы выехали из столицы). Пары в выходном файле должны быть упорядочены по времени прибытия гонца.