L. Сколько кратчайших путей

Посчитайте количество кратчайших путей из вершины 1 в вершину $n$ во взвешенном графе. Ответ выведите по модулю $10^9 + 7$.

Схема та же, что была для невзвешенного графа: сначала расстояния, потом счёт по возрастанию расстояния.

Единственное, что нужно поменять: вершины перебираются в порядке возрастания $\mathrm{dist}$, а не по слоям обхода в ширину. Дейкстра как раз снимает их с кучи в этом порядке, так что можно считать прямо во время работы алгоритма — либо отсортировать вершины после.

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

Кратные рёбра между одной парой вершин считаются разными путями, если оба лежат на кратчайшем.

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

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

Одно число — количество кратчайших путей по модулю $10^9 + 7$, или $0$, если пути нет.