Напишіть програму, яка знаходитиме відстані в неорієнтованому зваженому графі з невід'ємними довжинами ребер, від зазначеної вершини до всіх інших. Програма повинна працювати швидко для великих розріджених графів.

Вхідні дані

У першому рядку вхідних даних задано число NUM – кількість різних запусків алгоритму Дейкстри (на різних графах). Далі слідують NUM блоків, кожен з яких має таку структуру.

Перший рядок блоку містить два числа N і M, розділені пропуском – кількість вершин і кількість ребер графа. Далі слідують M рядків, кожен з яких містить по три цілих числа, розділені пробілами. Перші два з них в межах від 0 до N–1 кожне і позначають кінці відповідного ребра, третє – в межах від 0 до 20000 і позначає довжину цього ребра. Далі, в останньому рядку блоку, записане єдине число від 0 до N–1 – вершина, відстані від якої треба шукати.

Кількість різних графів в одному тесті NUM не перевищує 5. Кількість вершин не перевищує 60000, ребер – 200000.

Результати

Виведіть NUM рядків, у кожному з яких по ~N_i~ чисел, розділених пропусками – відстані від зазначеної початкової вершини зваженого неорієнтованого графа до його 0-ї, 1-ї, 2-ї і т. д. вершин. Якщо деяка вершина недосяжна від зазначеної початкової, замість відстані виводите число 2009000999 (гарантовано, що всі реальні відстані менші).

Приклади

Вхід

1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1

Результат

18 0 5 2 8

Примітки

Переконайтеся, що програма правильно враховує, що за один запуск слід обробити кілька різних графів.

Щоб забезпечити асимптотичну оцінку часу виконання ~O(M\log N)~, слід:

1. Подавати граф списками суміжності і робити перебір сусідів аналогічно задачі «Пошук в ширину — 1». (Однак, списками суміжності слід подати зважений граф, тому елементами списків повинні бути вже не числа, а, наприклад, структури з двох полів (вершина, куди йде ребро, і довжина цього ребра).)

2. При виборі, яка саме вершина статусу 1 має найнижчу оцінку відстані, користуватися деякою структурою даних, що вміє робити це ефективно. Зокрема (але не тільки), це може бути будь-який з таких способів:

   • деяка реалізація priority queue, наприклад, піраміда;
   • SortedSet.

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

Додаткову проблему створює те, що при виконанні алгоритму Дейкстри можлива зміна оцінки відстані до вершини статусу 1 (новий маршрут виявляється коротшим, чим знайдений раніше), після чого піраміда (чи SortedSet, чи ще якийсь аналог) має містити новий примірник структури/класу з тією ж вершиною, але меншою оцінкою відстані. Якщо лише вставляти новий примірник додатково до старого, це призводитиме до багатократного виймання з піраміди (чи SortedSet'а, чи ще якогось аналога) однієї й тієї ж вершини. Якщо таких вершин чимало, і з них виходить чимало ребер – це може призводити до істотного сповільнення роботи всього алгоритму. Наприклад, неважко побудувати граф, де оцінка відстані деякої вершини зменшується ~\approx0,4\cdot N~ разів, і саме з цієї вершини виходить ~\approx0,5\cdot N~ ребер. Погана реалізація алгоритму Дейкстри може ~\approx(0,4\cdot N)-1~ разів переглядати оцінки всих цих ~\approx0,5\cdot N~ вершин (без жодної на те потреби, бо саме в цьому випадку пізніше побудовані оцінки будуть гіршими (більшими) за раніше побудовані). Тобто, погана реалізація алгоритму Дейкстри запросто може виконати ~O(N^2)~ відверто зайвої роботи, що у випадку розріджених графів прямо протирічить меті «реалізувати алгоритм Дейкстри складністю ~O(M\log N)~». І в тестах цієї задачі такі (та ще деякі схожі) випадки є.

Щоб уникати таких непродуктивних ситуацій, варто забезпечити одну з двох властивостей:

• коли для деякої вершини зменшується оцінка відстані, відповідний примірник структури/класу слід вийняти з тієї структури даних, що використовується для пошуку мінімальної оцінки – так, щоб там взагалі ніколи не було кількох різних примірників, відповідних одній і тій самій вершині;
• коли деякий примірник структури/класу виймають з тієї структури даних, що використовується для пошуку мінімальної оцінки, треба додатково перевірити, чи така сама вершина ще не була вийнята раніше (іншими словами, чи вершина все ще статусу 1, а не статусу 2).

(Яку з цих властивостей краще підтримувати? Якщо використовувати піраміду, то асимптотично ефективно забезпечити першу властивість важко (піраміда не підтримує ефективних вилучень не кореневих елементів), а другу неважко, тому варто забезпечувати другу. Якщо використовувати буквально SortedSet мови C#, то забезпечувати першу стає легше (підтримання другої при цьому не ускладнюється), й тому більш-менш байдуже. Чи можна забезпечувати відразу обидві ці властивості? Можна, але не варто, бо будь-яка одна вже позбавить від вищезгаданої відверто зайвої роботи.)