I. Подземная система

Метро состоит из $N$ станций и $M$ линий. Линия $i$ соединяет станции $p_i$ и $q_i$, и ею управляет компания $c_i$.

Сесть на поезд стоит один бурль. Пересадка на линию той же компании бесплатна, на линию другой компании — снова один бурль.

Найдите наименьшую стоимость проезда от станции 1 до станции $N$.

Вершина здесь — не станция, а пара «станция и компания последней линии». Переход стоит ноль, если компания та же, и один иначе. Веса нулевые и единичные — это 0-1 BFS: очередь заменяется дэком, нулевые переходы кладутся в начало, единичные в конец.

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

Далее идут $M$ строк с тройками $p_i$, $q_i$, $c_i$ ($1 \le c_i \le 10^6$).

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