Задано зважений орієнтовний граф та вершина s у ньому. Для кожної вершини u виведіть довжину найкоротшого шляху від s до u.
Перший рядок містить три цілих числа n, m, s (2 ≤ n ≤ 2000, 1 ≤ m ≤ 5000) - кількість вершин та ребер у графі і номер початкової вершини відповідно.
Наступні m рядків описують ребра графа. Кожне ребро задається трьома числами - початковою вершиною, кінцевою вершиною та вегою ребра відповідно. Вага ребра - ціле число, яке не перевищує 10^15
за абсолютною величиною. У графі можуть бути кратні ребра та петлі.
Виведіть n рядків - для кожної вершини u виведіть довжину найкоротшого шляху з s в u. Якщо не існує шляху між s та u, виведіть "\*". Якщо не існує найкоротшого шляху між s і u, виведіть "-".