카트라이더

카트라이더는 플레이어가 주어진 맵에서 차를 타고 출발 지점에서 시작해 경로를 따라 목적지까지 최대한 빨리 도착하는 것이 목표인 게임이다.

이때 맵에는 다양한 지름길이 존재하여 목적지까지 갈 수 있는 방법은 다양하다.

카트라이더의 맵은 다음과 같은 무방향 가중 그래프로 나타낼 수 있다.

<그림 1> 예제 입력1 예시

카트라이더는 레이싱 게임이기 때문에 플레이어는 일정 속도로 이동한다.

플레이어는 1의 속도로 출발지에서 생성되고, 출발지를 포함한 모든 정점을 방문할 때마다 속도를 1 증가, 1 감소, 또는 그대로 유지할 수 있다. 시작 직후 출발지에서 속도를 올리는 것도 가능하다.

속도는 1 미만으로 내려갈 수 없다.

정점 사이의 간선은 길을 뜻하고, 간선은 길이와 속도 제한을 가진다.

간선을 통과할 때에는 길이를 속도로 나눈 만큼의 시간이 소모된다.

길의 코스가 어려운 구간에서는 속도가 빠르면 벽에 충돌할 수 있기 때문에 속도 제한을 넘긴 상태일 때에는 그 길을 사용할 수 없다.

카트라이더 맵이 주어졌을 때 출발 지점에서 목적지까지 이동할 때 걸리는 최단 시간을 구하여라.

첫번째 줄에는 정점의 개수 N 과 간선의 개수 M 이 차례로 주어진다. (2 ≤ N ≤ 10,000, 1 ≤ M ≤ 100,000)

다음 M 개의 줄에는 각 간선의 정보인 4개의 정수가 주어진다.

간선이 연결하는 정점 A, 정점 B, 간선의 길이 L, 속도 제한 K 가 차례로 주어진다. (1 <= A, B <= N, 1 <= L <= 100,000, 1 <= K <= 10)

1번 정점은 출발지이고, N 번 정점은 목적지이다.

입력으로 주어진 그래프는 출발지에서 목적지까지 이동할 수 있는 경로가 항상 존재한다.

출발지에서 목적지까지 이동하는데 필요한 최소 시간을 출력해라.

출력 값은 정확히 소수점 9자리까지 반올림하여 출력해야 한다.

double, long double 등의 실수형을 사용하여 출력할 경우 유효 숫자 범위로 인해 틀릴 수 있다.