B. На какой фазе установилось

Как классная задача B, но для каждой вершины выведите номер фазы, после которой её расстояние перестало меняться.

Для источника это ноль. Для недостижимых вершин выведите $-1$. Для остальных — номер последней фазы, на которой значение изменилось; фазы нумеруются с единицы.

Считать это просто: при каждом улучшении записывать в вершину номер текущей фазы. Никакого второго прохода не нужно.

Полезно посмотреть на распределение: обычно почти все вершины устаканиваются за одну-две фазы, а хвост из нескольких вершин тянет весь алгоритм. Именно поэтому ранняя остановка так помогает.

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

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

Одна строка из $n$ чисел.