C. Сам путь с отрицательными весами

Найдите кратчайший путь из вершины 1 в вершину $n$ и выведите его. Отрицательных циклов нет.

Массив предков здесь ненадёжен. С отрицательными весами рёбра «кратчайшего графа» не обязаны вести от меньшего расстояния к большему, а если в графе есть цикл нулевого веса, цепочка предков может замкнуться сама на себя — и восстановление зациклится.

Надёжнее считать по слоям. Пусть $d_k[v]$ — наименьший вес пути из вершины 1 в $v$, использующего не более $k$ рёбер. Слои считаются друг из друга ровно одной фазой Форда — Беллмана, а восстановление идёт по убыванию номера слоя и потому обязано закончиться.

Чтобы ответ был единственным, зафиксируем:

• среди кратчайших путей берётся тот, где рёбер меньше всего;
• восстановление идёт от вершины $n$: на слое $k$ ищется наименьшая вершина $u$ с ребром $(u, v, w)$, для которой $d_{k-1}[u] + w = d_k[v]$;
• дальше переходим в $u$ и на слой $k-1$.

Такая вершина всегда существует, а номер слоя строго убывает — значит, зацикливание невозможно.

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

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

Если пути нет — одно число $-1$.

Иначе в первой строке вес пути, во второй — количество вершин, в третьей — сам путь.