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