A. Форд — Беллман

Дан ориентированный граф с целыми весами рёбер; веса могут быть отрицательными. Отрицательных циклов нет. Найдите расстояния от вершины 1 до всех остальных.

Дейкстра здесь не годится: её доказательство опиралось на то, что снятая с кучи вершина уже не улучшится, а с отрицательными рёбрами это неверно. Нужен другой алгоритм.

Первая строка содержит числа $n$ ($1 \le n \le 100$) и $m$ ($0 \le m \le 10^4$).

Далее идут $m$ строк с рёбрами: начало, конец и вес ($-100 \le w \le 100$). Возможны кратные рёбра и петли.

Одна строка из $n$ чисел — расстояния от вершины 1. Для недостижимых вершин выведите $30000$.