H. Доставка кефирчика

Планеты соединены кефиропроводами двух видов: по старому кефир идёт два года, по новому — один. Найдите наименьшее время доставки с планеты 1 на планету $n$.

Дейкстрой это решается, но здесь не нужно: весов всего два. Ребро веса два можно заменить двумя рёбрами веса один, добавив промежуточную вершину, — и обойтись обычным обходом в ширину.

Кефиропроводы двусторонние; возможны кратные и петли.

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

Далее идут $m$ строк с тройками $u$, $v$, $c$, где $c$ равно 1 или 2 — время в годах.

Одно число — наименьшее время или $-1$, если доставка невозможна.