L. Кратчайший и покороче

Среди всех путей наименьшего веса из вершины 1 в вершину $n$ найдите тот, в котором меньше всего рёбер, и выведите это количество.

Считается так же, как количество кратчайших путей в классной задаче L, только вместо суммы берётся минимум:

Перебор идёт в порядке возрастания расстояния — том самом, в котором Дейкстра снимает вершины с кучи.

Приём общий: как только у вас есть граф кратчайших путей — то есть рёбра, для которых равенство выполняется, — на нём считается любая динамика: число путей, минимум рёбер, максимум чего-нибудь. Сам граф ациклический, потому что веса положительны.

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

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

Одно число — наименьшее количество рёбер, или $-1$, если пути нет.