Problem Description

You are given an undirected graph with $n$ vertices and $m$ edges. The length of an edge $e$ is a pair $(c_e, t_e)$.

The length of a path $w$ is $(c_w, t_w) = (\sum_{e \in w} c_e, \sum_{e \in w} t_e)$.

A path $w$ is shorter than another path $w'$ if and only if their lengths are different and $c_w \le c_{w'}, t_w \le t_{w'}$.

Obviously, two paths may be incomparable, so there may be multiple shortest paths with different lengths between two vertices.

Find the number of distinct possible lengths among the shortest paths from $s$ to $e$.

Input Format

The first line contains four integers $n, m, s, e$.

The next $m$ lines each contain four integers $p, r, c, t$, representing the two endpoints of an edge and its length.

Output Format

Output one integer on a single line, your answer.

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 

Hint

Sample Explanation

Consider the following four paths:

0. $1 \to 2 \to 4$ (length $(4, 5)$).
1. $1 \to 3 \to 4$ (length $(4, 5)$).
2. $1 \to 2 \to 3 \to 4$ (length $(6, 4)$).
3. $1 \to 3 \to 2 \to 4$ (length $(4, 10)$).

Path 0 and path 1 are both shorter than path 3. There are two shortest-path lengths in total: $(4, 5)$ (path 0, path 1) and $(6, 4)$ (path 2).

Constraints

$1 \le s, e, p, r \le n \le 100$, $0 \le m \le 300$, $s \ne e$, $0 \le c, t \le 100$.

Notes

BalticOI 2002 Day2 A.

Due to the configuration of the custom scoring script parameters, evaluation statuses other than AC, WA, TLE, and MLE are not supported for display. If you get any other evaluation status, you will receive UKE.

Subtask #0 is the sample; Subtask #1 is the full testdata.

Translated by ChatGPT 5