The number of shortest paths

Input

The first line contains two integers: $N$ (the number of squares in the city) and $M$ (the number of streets). Then $M$ lines follow, each describing a street with three integers: the numbers of the two squares it connects and its length. No street connects a square to itself. The same pair of squares can be connected by multiple streets, possibly with different lengths. Each street can be used in both directions. Finally, the numbers $A$ and $B$ are given.

Constraints: 1 \leq N \leq 1000, 1 \leq M \leq 100000, 1 \leq A \leq N, 1 \leq B \leq N. The lengths of the streets are positive integers not exceeding $100000$.

Output

Output the number of shortest paths between squares $A$ and $B$. If it is not possible to reach square $B$ from square $A$, output 0.

Examples