Magic Potion and the Critical Road

Baltazar is preparing for a vacation. He is in Baltazargrad (city 1) and plans to travel to Primosten (city n). There are n cities connected by m bidirectional roads. Each road has a given length in kilometers. Normally, Baltazar uses his GPS which always suggests a shortest route from city 1 to city n with distance \(d\).

Baltazar, being a true traveler, can use a magic potion exactly once. When applied to any road (even one he does not traverse), the length of that road increases by \(2\) kilometers. However, since he must check in at the Zora Hotel in Primosten before noon, he cannot afford too much delay. In particular, he wants to know on how many roads he can use the potion so that the overall shortest route distance increases by exactly \(1\) kilometer, i.e. from \(d\) to \(d+1\).

Note: The magic potion is applied before starting the journey. So, for the chosen road, its length becomes \(w+2\) while all other roads retain their original lengths. Baltazar will then follow the new shortest route from city 1 to city n. If there exists any alternative route that avoids the modified road and still gives a distance of \(d\), he would choose that route; hence the potion would have no effect. Therefore, the potion can only cause exactly a \(1\) km increase if the road is critical — meaning every shortest route in the original graph uses that road — and if the best alternative route not using that road is exactly \(d+1\).

Your task is to count the number of roads satisfying this property.

Input Format: In the input, the first line contains two integers \(n\) and \(m\) (the number of cities and roads respectively). The following \(m\) lines each contain three integers \(u\), \(v\), and \(w\), which denote a bidirectional road between cities \(u\) and \(v\) with length \(w\) kilometers.

Output Format: Output a single integer representing the number of roads such that if the magic potion is applied on that road, the new shortest path from city 1 to city n increases by exactly \(1\) kilometer (i.e. becomes \(d+1\)).

inputFormat

The first line contains two space-separated integers \(n\) and \(m\) (\(2 \le n \le 10^4\); \(1 \le m \le 5 \times 10^4\)), representing the number of cities and roads respectively.

Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\) (\(1 \le u,v \le n\); \(1 \le w \le 10^3\)), indicating that there is a bidirectional road between cities \(u\) and \(v\) with length \(w\) kilometers.

outputFormat

Output a single integer — the number of roads on which using the magic potion will cause the shortest path distance from city 1 to city n to increase from \(d\) to exactly \(d+1\).

sample

4 4
1 2 1
2 4 1
1 3 2
3 4 1

2