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