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

Форд-Беллман

Форд-Беллман

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.

Входные данные

Сначала записано количество вершин графа n (1n100), за которым идет количество ребер m (0m10000). Следующие m троек чисел описывают ребра: начало ребра, конец ребра и его вес (вес - целое число от -100 до 100).

Выходные данные

Выведите n чисел - расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

Пример

Входные данные #1
4 5
1 2 10
2 3 10
1 3 100
3 1 -10
2 3 1
Выходные данные #1
0 10 11 30000