Counting Tour Routes

A tour operator organizes guided bus trips across a region. Each day, the bus travels from a fixed starting city S to a fixed destination F along a sequence of roads. The bus may stop at several cities along the way, and different routes from S to F are considered distinct if there is at least one road from some city A to city B which is used in one route but not in the other.

To ensure there is enough time for sightseeing as well as to limit fuel consumption, the bus is only allowed to take routes whose total distance is either the minimal distance from S to F, or exactly one unit longer than the minimal distance. In other words, if we denote the minimal distance from S to F by \(d\), the valid routes have total distance either \(d\) or \(d+1\).

Two routes are considered different if their set of roads differs. Given a (partial) road map of the region and two cities S and F, your task is to calculate how many distinct routes satisfy the length restriction.

Note: It is guaranteed that all road distances are positive integers, and the road network is directed.

Input Format

The input will be given in the following format:

 n m
 u1 v1 w1
 u2 v2 w2
 ...
 um vm wm
 S F

Here, \(n\) is the number of cities and \(m\) is the number of roads. Each of the next \(m\) lines contains three integers \(u, v, w\) indicating there is a directed road from city \(u\) to city \(v\) with distance \(w\). The final line contains two integers \(S\) and \(F\) representing the starting and final cities respectively.

Output Format

Output a single integer, which is the total number of valid routes from S to F. A valid route is one whose total distance is either the minimal distance \(d\) or \(d+1\), where \(d\) is the length of a shortest path from S to F.

You may assume that the answer fits in a 64-bit signed integer.

inputFormat

The first line contains two space‐separated integers \(n\) and \(m\), representing the number of cities and roads respectively.

The following \(m\) lines each contain three integers \(u, v, w\) describing a directed road from city \(u\) to city \(v\) with distance \(w\) (with \(w > 0\)).

The last line contains two integers \(S\) and \(F\) representing the starting city and the final city respectively.

outputFormat

Output a single integer: the total number of valid routes from \(S\) to \(F\) that have total distance equal to either the minimal distance \(d\) or \(d+1\).

sample

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

3