Counting Shortest Paths in a Directed Graph

In this problem, you are given a directed graph representing towns and roads. The graph consists of $N$ nodes (towns) and $M$ directed edges. Town $1$ is the starting point and town $N$ is the destination. Each edge from town $I$ to town $J$ requires $D[I,J]$ time. Your task is to find the number of distinct shortest paths from town $1$ to town $N$. Two paths are considered different if the sequence of towns is different. If there is no path from town $1$ to town $N$, output $0$.

inputFormat

The first line contains two integers $N$ and $M$, representing the number of towns and the number of directed roads, respectively. Each of the following $M$ lines contains three integers $I$, $J$, and $D$, representing a one-way road from town $I$ to town $J$ with a travel time of $D$.

outputFormat

Output a single integer representing the number of distinct shortest paths from town $1$ to town $N$.

sample

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

2