Reasonable Paths

Time limit2sMemory limit128 MB

Summary
Given a weighted undirected graph, count paths from vertex 1 to vertex 2 where each step moves to a vertex strictly closer to vertex 2 by shortest-path distance.
Level

Medium6 of 10

Topics
Shortest path, Graph, Dynamic programming
Solved
No attempts yet

Problem

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.

Input

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.

Output

Print the number of reasonable paths on the first line.

The answer does not exceed 2147483647.

Examples1

  1. Example 1

    Input
    4 4
1 3 1
3 2 2
1 4 2
2 4 1
    Expected output
    2