Count Distinct Shortest Path Lengths

Given an undirected graph with \(n\) vertices and \(m\) edges, where each edge \(e\) has a length tuple \(\left(c_e, t_e\right)\). The length of a path \(w\) is defined as \[ \left(c_w, t_w\right)=\left(\sum_{e \in w} c_e, \; \sum_{e \in w} t_e\right). \]

We say that a path \(w\) is shorter than another path \(w'\) if and only if their lengths are different and \[ c_w \le c_{w'} \quad \text{and} \quad t_w \le t_{w'}. \]

Note that it is possible that two paths are not comparable under this definition, which may result in multiple distinct shortest path length values between two vertices.

Your task is to compute the number of distinct shortest path length pairs from a given source vertex \(s\) to a target vertex \(e\).

inputFormat

The input begins with a line containing four integers \(n, m, s, e\) where \(1 \leq s,e \leq n\).

Then \(m\) lines follow. Each of these lines contains four integers \(u, v, c, t\), representing an undirected edge between nodes \(u\) and \(v\) with length tuple \(\left(c, t\right)\).

outputFormat

Output a single integer, which is the number of distinct shortest path length pairs from vertex \(s\) to vertex \(e\). If there is no path from \(s\) to \(e\), output 0.

sample

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

1