Задача Java. Динамическое программирование

На всем известной красной планете после успешной высадки людей было основано новое государство, состоящее из n городов, которые для удобства получили номера от 1 до n. Их некоторым образом соединяют m сверхинновационных дорог, для каждой из которых известно время, которое необходимо затратить, чтобы добраться по ней из одного города в другой.

Кроме того, в результате всеобщего голосования, была выбрана столица, в которой расположились главные научные центры. Это позволило в скором времени совершить в столице открытие, ранее считавшееся невозможным. Конечно, в первую очередь, необходимо оповестить о нем людей в k

k определенных городах. Для доставки сообщения используются колесные роботы, способные передвигаться по дорогам. Все роботы выезжают из столицы одновременно.

Ваша задача - узнать в каком порядке и через какое время роботы доставят сообщения во все нужные города. Во время всего пути роботы непрерывно едут, пока не достигнут точки назначения. Временем на пересечение городов можно пренебречь.

В первой строке записаны четыре числа n, m, k, c (2 ≤ n ≤ 1000, 1 ≤ m ≤ 10000, 1 ≤ k ≤ n, 1 ≤ c ≤ n) — количество городов, количество дорог, количество городов, в которые необходимо доставить сообщение и номер столицы.

Во второй строке даны k чисел, задающие номера городов, в которые необходимо доставить сообщение.

В следующих строках располагаются m троек чисел si , fi , ti  (1 ≤ si ≤ n, 1 ≤ fi ≤ n, si ≠ fi, 1 ≤ ti ≤ 100), описывающих дороги - si , fi  - номера городов, которые соединяет описываемая дорога, а ti - время, которое необходимо затратить, чтобы проехать по данной дороги из города si  в fi .

Гарантируется, что все города достижимы из столицы.

Необходимо вывести 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