The number of shortest paths
In the city, there are N squares connected by roads, each with a known length.
Your task is to determine the number of shortest paths from square A to square B.
Input
You are given the number N, representing the total number of squares in the city, and M, the number of streets. Following this, the details of each street are provided. Each street is described by three numbers: the two squares it connects and the length of the street. No street connects a square to itself, and multiple streets can connect the same pair of squares, potentially with different lengths. Each street is bidirectional. Finally, the numbers A and B are provided.
Constraints: 1 ≤ N ≤ 1000, 1 ≤ M ≤ 100000, 1 ≤ A ≤ N, 1 ≤ B ≤ N. The lengths of the streets are natural numbers not exceeding 100000.
Output
Output the number of shortest paths from square A to square B. If square B cannot be reached from square A, output 0.