У країні алхіміків є \(N\) населених пунктів, пронумерованих числами від 1 до \(N\), та \(M\) доріг. Населені пункти бувають двох типів: села та міста. Крім того, в державі є одна столиця (вона може розташовуватися як у місті, так і на селі). Кожна дорога з'єднує два населені пункти, і для проїзду нею потрібно \(T_i\) хвилин. У столиці було вирішено провести 1-у державну командну олімпіаду з алхімії. Для цього у всі міста зі столиці було відправлено гінців (по одному гінцю на місто) з інформацією про олімпіаду.

Напишіть програму, яка визначить, в якому порядку і через який час кожен із гінців дістанеться свого міста. Вважається, що гонець під час свого шляху не спить і ніде не затримується.

Формат вхідних даних

У вхідному потоці спочатку записані 3 числа \(N, M, K\) — кількість населених пунктів, кількість доріг і кількість міст (\(2 \le N \le 1000\), \(1 \le M \le 10000\), \(1 \le K \le N\)).

Далі записано номер столиці \(C\) (\(1 \le C \le N\)).

Наступні \(K\) чисел задають номери міст.

Далі йдуть \(M\) трійок чисел \(S_i, E_i, T_i\), що описують дороги: \(S_i\) та \(E_i\) — номери населених пунктів, які з'єднує ця дорога, а \(T_i\) — час для проїзду нею (\(1 \le T_i \le 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