Unique Shortest Paths

You are given a directed graph representing a city's road network with N intersections (numbered from 0 to N-1) and M one-way roads. Each road goes from one intersection to another with a certain travel time (or weight). Your task is to find the number of unique shortest paths from intersection 0 to a specified intersection L.

More formally, let \( d(u,v) \) denote the shortest distance from vertex \( u \) to vertex \( v \). We desire the total number of distinct paths from vertex 0 to vertex \( L \) such that the path length is \( d(0,L) \). If there is no path from 0 to \( L \), the answer should be 0.

Note: Two paths are considered different if the sequence of visited intersections differs, even if their total travel time is the same.

inputFormat

The input is read from stdin and is structured as follows:

• The first line contains three integers: N (the number of intersections), M (the number of roads), and L (the target intersection).
• The next M lines each contain three integers u, v, and w, representing a one-way road from intersection u to intersection v with a travel time of w.

outputFormat

Output a single integer to stdout — the number of unique shortest paths from intersection 0 to intersection L. If no such path exists, output 0.

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

2