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

[Daniia]

Алгоритм Форда-Беллмана

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

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

Входные данные
В первой строке записаны целые числа N и M - количество вершин и количество ребер графа (1 ≤ N ≤ 100, 0 ≤ M ≤ 10000). В каждой из последующих M строк записана тройка чисел, описывающих ребра: начало ребра, конец ребра и вес (вес - целое число от -100 до 100).

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

Например, вход:
4 5
1 2 10
2 3 10
1 3 100
3 1 -10
2 3 1

выход: 0 10 11 30000

надеюсь, код будет не с миллионом всяких крутых процедур и тд, чтобы было понятно. Нужно к завтрашнему утру
спасибо!

[MansMI]

пишите, почта в подписи