고속도로

여러 도시를 잇는 양방향 고속도로망이 있다. 각 도로에는 이용 요금과 통과 시간이 정해져 있다.

시작 도시에서 도착 도시까지 가는 경로의 총 요금은 사용한 도로 요금의 합이고, 총 시간은 사용한 도로 시간의 합이다. 어떤 경로 A의 총 요금이 경로 B보다 크지 않고 총 시간도 경로 B보다 크지 않으며, 둘 중 하나 이상이 더 작다면 A가 B보다 더 좋은 경로이다.

어떤 요금-시간 쌍을 만드는 경로가 존재하고, 그 쌍보다 더 좋은 다른 경로가 없다면 그 요금-시간 쌍을 효율적이라고 한다. 서로 다른 경로가 같은 요금-시간 쌍을 만들면 하나로 센다.

고속도로망과 시작 도시, 도착 도시가 주어질 때, 시작 도시에서 도착 도시까지 갈 수 있는 서로 다른 효율적인 요금-시간 쌍의 개수를 구하라.

첫째 줄에 도시의 개수 n, 도로의 개수 m, 시작 도시 s, 도착 도시 e가 주어진다.

• 1 <= n <= 100
• 1 <= m <= 300
• 1 <= s, e <= n
• s != e

다음 m개의 줄에는 도로 정보가 한 줄에 하나씩 주어진다. 각 줄에는 도로의 양 끝 도시 p, r, 이용 요금 c, 통과 시간 t가 주어진다.

• 1 <= p, r <= n
• p != r
• 0 <= c <= 100
• 0 <= t <= 100

두 도시 사이에 도로가 여러 개 있을 수 있다.

시작 도시에서 도착 도시까지 갈 수 있는 서로 다른 효율적인 요금-시간 쌍의 개수를 출력한다.