퇴근 시간

회사는 서울의 1번 지점에 있다. 서울은 N개의 지점으로 나뉘고, 각 지점에는 1번부터 N번까지 번호가 붙어 있다. M개의 도로가 서로 다른 두 지점을 잇고, 어느 지점에서든 다른 모든 지점으로 이동할 수 있다. 도로마다 길이가 있고, 막히지 않은 도로에서는 거리 1을 지나는 데 1분이 걸린다.

직원은 모두 0분에 회사를 나선다. 퇴근 시간은 S분부터 E분까지다. 이 시간 동안 정체되는 도로는 속도가 절반으로 떨어져서 거리 1을 지나는 데 2분이 걸린다. 정체 여부는 도로마다, 그리고 진행 방향마다 따로 정해진다. 퇴근 시간에도 막히지 않는 도로가 있다.

퇴근 시간이 10분부터 20분까지이고, 길이가 10인 정체 도로에 15분에 진입한 경우를 보자.

• 15분부터 20분까지 5분 동안 거리 2.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)

다음 M개의 줄에는 도로가 잇는 두 지점 A와 B, 도로의 길이 L, 정체 여부를 뜻하는 t1과 t2가 주어진다. (1 ≤ A, B ≤ N, A ≠ B, 1 ≤ L ≤ 1,000,000,000, t1과 t2는 0 또는 1)

• t1이 1이면 퇴근 시간에 A에서 B로 이동할 때 정체된다.
• t2가 1이면 퇴근 시간에 B에서 A로 이동할 때 정체된다.
• 0이면 그 방향으로는 정체되지 않는다.

같은 두 지점을 잇는 도로가 여러 개 있을 수 있다.

회사에서 출발했을 때 가장 늦게 도착하는 지점의 도착 시각을 첫째 줄에 출력한다.

답은 항상 0.5의 배수다. 답이 정수이면 소수점 없이 출력하고, 정수가 아니면 소수점 아래 한 자리까지 출력한다.

첫 번째 예제의 도로망은 다음과 같다. 분홍색으로 칠한 구간이 퇴근 시간에 정체되는 방향이다.

퇴근 시간이 없다면 가장 늦게 도착하는 지점은 15분에 도착하는 7번이다. 하지만 3번으로 가는 경로가 정체되기 때문에 16분에 도착하는 3번이 가장 늦다.

• 1번 도로: 거리 5를 5분 동안 지나면 퇴근 시간이 시작되고, 남은 거리 3을 6분 동안 지난다. 모두 11분이 걸린다.
• 2번 도로: 2분 동안 거리 1을 지나면 퇴근 시간이 끝나고, 남은 거리 3을 3분 동안 지난다. 모두 5분이 걸린다.

합해서 16분이다.