Reasonable Paths

You are given an undirected weighted graph and want to move from vertex 1 to vertex 2.

A vertex is closer to vertex 2 if its shortest-path distance to vertex 2 is smaller. A path is reasonable if every move goes from the current vertex to a vertex that is closer to vertex 2. Such a path does not have to be a shortest path overall.

Given the graph, count how many reasonable paths are possible.

The first line contains the number of vertices N and the number of edges M.

• 1 < N <= 1,000
• 1 <= M <= 100,000

Each of the next M lines contains three integers A, B, and C, describing an edge of length C between vertices A and B.

• 0 < C <= 10,000
• There is at most one edge between any pair of vertices.
• All edges are undirected.

Print the number of reasonable paths on the first line.

The answer does not exceed 2147483647.