카트라이더

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

맵에는 다양한 지름길이 있어서 목적지까지 가는 방법이 여러 가지다.

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

그림 1

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

플레이어는 속도 1로 출발 지점에서 생성된다. 출발 지점을 포함해 정점을 방문할 때마다 속도를 1 올리거나, 1 내리거나, 그대로 유지할 수 있다. 출발 직후 출발 지점에서 속도를 올리는 것도 가능하다.

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

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

간선을 통과할 때는 길이를 속도로 나눈 만큼의 시간이 걸린다.

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

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

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

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

간선이 잇는 정점 $A$, 정점 $B$, 간선의 길이 $L$, 속도 제한 $K$가 차례로 주어진다. ($1 \le A, B \le N$, $1 \le L \le 100,000$, $1 \le K \le 10$)

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

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

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

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

double이나 long double 같은 실수형을 사용해 출력하면 유효 숫자 범위 때문에 틀릴 수 있다.