M. Одна дорога бесплатно

Дан неориентированный взвешенный граф. Ровно один раз за поездку разрешается проехать по дороге бесплатно — не обязательно пользоваться этим правом. Найдите наименьшую стоимость пути из вершины 1 в вершину $n$.

Опять граф состояний, и вершина — пара «где я и потратил ли я бесплатный проезд».

Вершин $2n$, рёбер $3m$, дальше — обычная Дейкстра. Ответ — наименьшее из двух состояний в вершине $n$.

Такой приём называют слоями: граф копируется столько раз, сколько различных «положений дел» бывает, и переходы между слоями отвечают за расход ресурса. Слоёв может быть и больше двух — например, «разрешено $k$ бесплатных проездов» даёт $k + 1$ слой.

Что важно не перепутать: бесплатный проезд обнуляет вес ребра, а не пропускает вершину. И воспользоваться им можно не более одного раза за всю поездку, а не один раз в каждой вершине.

Первая строка содержит числа $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$.