엔지니어의 행복도는 퇴근 후 집에 도착하는 시각이 늦을수록 낮아진다는 것이 증명되었다.</p>

조이의 대표 레드는 엔지니어의 행복도를 최대한 높여야 할 의무가 있기 때문에, 신중하게 퇴근 시간을 조정하기로 하였다.

하지만 퇴근 시간을 조정하려면 먼저 엔지니어들이 집에 도착하는 시간을 알아야만 했다.

이 문제를 미카에게 맡기려고 했지만, 6시가 넘어 미카는 이미 퇴근해버렸기 때문에 레드는 고민에 빠지고 말았다.

레드를 도와 레드와 조이 엔지니어 모두의 행복도를 높여보도록 하자!

회사가 있는 서울은 N개의 지점으로 되어있다.

각 지점은 1번부터 N번의 번호를 가지고 있고, 회사는 1번 지점에 있다.

M개의 도로들은 서로 다른 지점을 연결하고 있으며, 임의의 지점에서 모든 지점으로 이동할 수 있다.

각각의 도로는 길이를 가지고 있으며, 거리 1을 이동하는 데 1분이 걸린다.

편의상 퇴근은 0분에 한다고 가정한다.

서울은 퇴근 시간에 도로가 막힌다.

퇴근 시간이 아닐 때에는 거리 1을 이동하는 데 1분이 걸리지만,

퇴근 시간이 겹칠 경우 혼잡한 도로는 거리 1을 이동하는 데 2분이 걸리게 된다. (물론 퇴근 시간에 막히지 않는 도로도 있다.)

만약 퇴근 시간이 10분부터 20분이고 어떤 도로에 진입한 순간이 15분이며, 도로의 길이는 10이라면 이 도로를 전부 통과하는 데 걸리는 시간은

• 퇴근 시간 : 5분(15 ~ 20분)동안 간 거리 = 2.5를 가는 데 걸린 시간 : 5분
• 퇴근 시간 외의 시간 : 나머지 거리 7.5를 가는 데 걸린 시간 : 7.5분

총 12.5분이 된다.

입력 형식

첫째 줄에는 N, M과 퇴근 시간의 시작과 끝을 의미하는 S와 E가 정수로 주어진다. (2 ≤ N ≤ 5,000, 1 ≤ M ≤ 100,000, 0 ≤ S < E ≤ 1,000,000,000)</p>

다음 M개의 줄에는 서로 다른 정수 A, B와 도로의 길이를 의미하는 L, 그리고 t1, t2가 주어진다. (1 ≤ A, B ≤ N, 1 ≤ L ≤ 1,000,000,000, t1, t2 = 0 또는 1)

t1, t2는 A,B 사이에 퇴근 시간에 도로가 정체되는지 여부이다.

• t1 = 1 일 때는 퇴근 시간에 A에서 B로 이동시 정체됨을 의미하며,
• t2 = 1 일 때는 퇴근 시간에 B에서 A로 이동시 정체됨을 의미한다.
• 만약 t1 혹은 t2가 0이라면 각각의 이동시 정체되지 않음을 의미한다.

퇴근할 때는 같은 길로는 2번 이상 이동하지 않는다. 사원들은 언제나 최대한 빨리 집에 가고 싶어하기 때문에 일부러 늦는 길을 선택하지 않는다. 또한 이동할 때 멈추지 않고 계속 이동한다.

출력 형식

모든 지점에 대해서 회사에서 출발했을 때 가장 늦게 도착하게 되는 지점까지의 도착 시각을 첫째 줄에 출력하라.

예제 입력 1

7 6 5 13
1 2 8 1 0
3 2 4 0 1
1 5 5 0 0
1 4 10 0 0
1 6 10 0 0
6 7 5 0 0

예제 출력 1

16

예제 입력 2

7 6 4 13
1 2 8 1 0
3 2 4 0 1
1 5 5 0 0
1 4 10 0 0
1 6 10 0 0
6 7 5 0 0

예제 출력 2

16.5

힌트

퇴근 시간이 없다면 7번에 도착하는 시각인 15분이 가장 늦게 된다.

하지만 3번까지 가는 경로가 정체가 되기 때문에 3번에 도착하는 시각이 16분으로 가장 늦게 된다.

• 1번 도로 : 5만큼 5분간 이동 -> 퇴근 시간 시작 -> 나머지 3을 6분동안 이동 : 11분만에 이동
• 2번 도로 : 2분동안 1만큼 이동 -> 퇴근 시간이 끝남 -> 나머지 3을 3분동안 이동 : 5분
</ul>

합 16분

• 조이는 ICPC 문제 풀이 능력을 중요하다고 생각하고 있습니다.
• 이 문제를 푼 분에게는 조이코퍼레이션 지원 시 선착순 10명에게 서류전형 통과의 기회를 드리고 있습니다.
• 이외에도 BOJ문제를 많이 푸신 분은 지원 시 어드밴티지가 있습니다.
• 자세한 채용 정보는 http://zoyi.co/job 에서 확인해주세요.