O. Рёбра на кратчайших путях

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

Двумя запусками Дейкстры — из вершины 1 и из вершины $n$. Обозначим $a[v]$ и $b[v]$ полученные расстояния, а $D = a[n]$. Ребро $(u, v)$ веса $w$ лежит на кратчайшем пути, если

Две проверки, потому что ребро неориентированное и пройти его можно в любую сторону.

Смысл равенства простой: слева — длина наилучшего пути, который обязан пройти по этому ребру. Если она равна $D$, ребро на каком-то кратчайшем пути лежит; если больше — не лежит ни на одном.

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

Если пути из 1 в $n$ нет, ответ — ноль.

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

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

Одно число.