Алгоритм Форда-Беллмана — это алгоритм поиска кратчайших путей от одной вершины до всех остальных в ориентированном взвешенном графе. В отличие от алгоритма Дейкстры, он может работать с рёбрами отрицательного веса и обнаруживать отрицательные циклы.

Алгоритм выполняет V-1 итераций релаксации всех рёбер, где V — количество вершин. После этого выполняется дополнительная проверка на наличие отрицательных циклов.

Временная сложность: O(V × E), где V — количество вершин, E — количество рёбер.

Введите квадратную матрицу весов построчно. Используйте запятую как разделитель. Допускаются отрицательные числа, 0 — отсутствие ребра.