eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

Вхідні дані

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

Наступні 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
-
-
-
*
Джерело 2005 Петрозаводск, Andrew Stankevich Contest 13, Август 24, Задача E