Населені пункти бувають двох типів: села і міста. Крім того, у державі є одна столиця (вона може розташовуватися як у місті, так і на селі). Кожна дорога з’єднує два населених пункти і для проїзду по ній потрібно Ті хвилин. У столиці було вирішено провести державну командну олімпіаду з інформатики. Для цього в усі міста зі столиці були відправлені гінці (по одному гінці до одного міста) з інформацією про олімпіаду. Напишіть програму, яка порахує, в якому порядку і за який час кожен з гінців дістанеться до свого міста. Вважаться, що гонець під час шляху не спить і ніде не затримується.
Формат вхідних даних.
У вхідному файлі спочатку записані 3 числа N, M, K – кількість населених пунктів, кількість доріг і кількість міст (2<=N<=1000, 1<=M<=10000, 1<=K<=N). Далі записано номер столиці С (1<=C<=N). Наступні К чисел задають номери міст. Далі йдуть М трійок чисел Si, Ei, Ti, що описують дороги: Si i Ei – номери населених пунктів, що з’єднує ця дорога, а Ті – час для проїзду по ній (1<=Ti<=100). Гарантується, що до кожного міста зі столиці можна дістатися по дорогах (можливо, через інші населені пункти).
Формат вихідних даних
Виведіть у вихідний файл К пар чисел: для кожного міста повинен бути виведений його номер і мінімальний час, коли гонець може в ньому появитися (час вимірюється в хвилинах з того моменту, як гінці виїхали зі столиці). Пари у вихідному файлі мають бути впорядковані за часом прибуття гінця.

Приклад

Input.txt                    Output.txt
5  4  5  1                    1  0
1  2  3  4  5                    2  1
1  2  1                        3  11
2  3  10                        4  111
3  4  100                    5  211
4  5  100

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

Буду сподіватись що на форумі є   ті  хто  розбереться в цьому.