M. Две дороги бесплатно

Как классная задача M, но бесплатных проездов теперь два — воспользоваться можно ноль, один или два раза.

Слоёв становится три: $(v, 0)$, $(v, 1)$, $(v, 2)$ — сколько бесплатных проездов уже израсходовано. Переходы те же: по ребру внутри слоя за его вес, по ребру между соседними слоями бесплатно.

Ответ — наименьшее из трёх состояний в вершине $n$.

Приём обобщается на любое $k$: слоёв $k + 1$, вершин $n(k+1)$, рёбер $m(2k+1)$. Именно так решаются задачи вида «можно $k$ раз сделать что-то особенное»: ресурс становится частью вершины.

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

Далее идут $m$ строк с рёбрами: концы и вес $w$ ($0 \le w \le 10^4$).

Одно число — наименьшая стоимость или $-1$.