Задачи
Кратчайшие пути
Кратчайшие пути
Задан взвешенный ориентированный граф и вершина 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 - - - *