Description

Original Source: BalticOI 2002

Road toll systems are rapidly evolving. With the increasing density of roads, choosing the optimal path has become a practical concern. The roads in the city are bidirectional, and each road has a fixed travel time and a cost associated with it.

A path consists of a sequence of connected roads. The total time is the sum of the travel times of the individual roads, and the total cost is the sum of the costs of the roads traversed. A path is considered better if it is either faster or cheaper than another path. More precisely, if a path is strictly faster and not more expensive, it is better. The converse also holds true. If no other path is better than a given path, that path is called a minimal path.

There may be multiple such minimal paths or none at all.

Problem: Read the network and compute the total number of distinct minimal paths. Two minimal paths with identical cost and time are considered the same. You only need to output the count of distinct minimal paths.

Input Format

The first line contains four integers: the total number of cities $n$, the total number of roads $m$, the starting city $s$, and the destination city $e$;

The next $m$ lines each describe a road with four integers: the two endpoints $p$ and $r$, the cost $c$, and the time $t$;

There may be multiple roads connecting the same pair of cities.

Output Format

A single integer representing the total number of distinct minimal paths.

Sample 1

Sample input as shown below:

There are 4 paths from $1$ to $4$. They are $1\to 2\to 4$ (cost $4$, time $5$), $1\to 3\to 4$ (cost $4$, time $5$), $1\to 2\to 3\to 4$ (cost $6$, time $4$), and $1\to 3\to 2\to 4$ (cost $4$, time $10$).

$1\to 3\to 4$ and $1\to 2\to 4$ are better than $1\to 3\to 2\to 4$. There are two optimal paths: one with cost $4$ and time $5$ ($1\to 2\to 4$ and $1\to 3\to 4$) and another with cost $6$ and time $4$ ($1\to 2\to 3\to 4$).

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

2

Data Range and Hints

For all data, $1\le n\le 100,0\le m\le 300,1\le s,e,p,r\le n,0\le c,t\le 100$. It is guaranteed that $s\not =e$ and $p\not =r$.