B. Сколько фаз хватило

Тот же граф и тот же алгоритм, но выводится не результат, а сколько фаз действительно понадобилось.

Фазой считается один проход по всем рёбрам в порядке ввода. Считаются только те фазы, на которых хоть одно расстояние изменилось: как только фаза прошла впустую, алгоритм останавливается, и она не засчитывается.

Ответ показывает, насколько ранняя остановка полезна. Верхняя граница $n - 1$ достигается редко — обычно на специально построенных графах, где рёбра перечислены «против» направления путей.

Полезно осознать: ответ зависит от порядка рёбов во входе. Тот же граф с переставленными рёбрами может сойтись за одну фазу или за $n-1$. Поэтому в условии порядок зафиксирован — это порядок ввода.

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

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

Одно число — количество результативных фаз.