Найкоротші шляхи

Задано зважений орієнтовний граф та вершина s у ньому. Для кожної вершини u виведіть довжину найкоротшого шляху від s до u.

Вхідні дані

Перший рядок містить три цілих числа n, m, s (2 ≤ n ≤ 2000, 1 ≤ m ≤ 5000) - кількість вершин та ребер у графі і номер початкової вершини відповідно.

Наступні m рядків описують ребра графа. Кожне ребро задається трьома числами - початковою вершиною, кінцевою вершиною та вегою ребра відповідно. Вага ребра - ціле число, яке не перевищує 10^15 за абсолютною величиною. У графі можуть бути кратні ребра та петлі.

Вихідні дані

Виведіть n рядків - для кожної вершини u виведіть довжину найкоротшого шляху з s в u. Якщо не існує шляху між s та u, виведіть "*". Якщо не існує найкоротшого шляху між s і u, виведіть "-".

Приклади