题目描述

原题来自：BalticOI 2002

如今的道路收费发展很快。道路的密度越来越大，因此选择最佳路径是很现实的问题。城市的道路是双向的，每条道路有固定的旅行时间以及需要支付的费用。

路径是连续经过的道路组成的。总时间是各条道路旅行时间的和，总费用是各条道路所支付费用的总和。一条路径越快，或者费用越低，该路径就越好。严格地说，如果一条路径比别的路径更快，而且不需要支付更多费用，它就比较好。反过来也如此理解。如果没有一条路径比某路径更好，则该路径被称为最小路径。

这样的最小的路径有可能不止一条，或者根本不存在路径。

问题：读入网络，计算最小路径的总数。费用时间都相同的两条最小路径只算作一条。你只要输出不同种类的最小路径数即可。

输入格式

第一行有四个整数，城市总数 \(n\)，道路总数 \(m\)，起点和终点城市 \(s,e\)；

接下来的 \(m\) 行每行描述了一条道路的信息，包括四个整数，两个端点 \(p,r\)，费用 \(c\)，以及时间 \(t\)；

两个城市之间可能有多条路径连接。

输出格式

仅一个数，表示最小路径的总数。

样例数据

样例输入

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

样例说明

样例输入如下图：

从 \(1\) 到 \(4\) 有 \(4\) 条路径。为 \(1\to 2\to 4\)（费用为 \(4\)，时间为 \(5\)），\(1\to 3\to 4\)（费用为 \(4\)，时间为 \(5\)），\(1\to 2\to 3\to 4\)（费用为 \(6\)，时间为 \(4\)），\(1\to 3\to 2\to 4\)（费用为 \(4\)，时间为 \(10\)）。

\(1\to 3\to 4\) 和 \(1\to 2\to 4\) 比 \(1\to 3\to 2\to 4\) 更好。有两种最佳路径：费用为 \(4\)，时间为 \(5\)（\(1\to 2\to 4\) 和 \(1\to 3\to 4\)）和 费用为 \(6\)，时间为 \(4\)（\(1\to 2\to 3\to 4\)）。

限制与提示

对于全部数据，\(1\le n\le 100,0\le m\le 300,1\le s,e,p,r\le n,0\le c,t\le 100\)，保证 \(s\not =e,p\not =r\)。