제국

지용이는 미적분학 교과서를 찢어서 사람 한 명이 탈 수 있는 두께 $K$의 뗏목을 만들었다. 이제 A 항구를 떠나 무인도 B에 자신의 제국을 세우러 갈 계획이다.

바다에는 섬이 $N$개, 바닷길이 $M$개 있다. 바닷길이 아닌 곳으로는 갈 수 없어서 지용이는 섬을 거쳐 가며 항해한다. $i$번 바닷길은 지나는 데 시간 $t_i$가 걸리고 뗏목을 $h_i$cm 깎아낸다.

지나온 바닷길의 $h_i$ 합이 $K$ 이상이 되면 뗏목의 두께가 0cm 이하가 되어, 수영을 못하는 지용이는 살아남지 못한다. 즉 지나온 바닷길의 $h_i$ 합이 $K$보다 작게 유지되는 동안만 항해가 안전하다.

A에서 B까지 안전하게 갈 수 있는 항로 중 걸리는 시간이 가장 짧은 것을 찾아 그 시간을 출력하자. 같은 섬이나 같은 바닷길을 여러 번 지나도 되며, 지날 때마다 시간과 깎이는 두께가 다시 더해진다.

첫째 줄에 정수 $K$, $N$, $M$이 주어진다. ($1 \le K \le 200$, $2 \le N \le 2000$, $1 \le M \le 10000$)

다음 $M$개의 줄에 바닷길 하나의 정보가 $u$, $v$, $t_i$, $h_i$ 형태로 주어진다. ($1 \le u, v \le N$, $u \ne v$, $1 \le t_i \le 100000$, $0 \le h_i \le 200$) 섬 $u$와 섬 $v$를 잇는 양방향 바닷길이 있고, 이 길을 지나는 데 시간 $t_i$가 걸리며 뗏목이 $h_i$만큼 깎인다는 뜻이다. 같은 두 섬을 잇는 바닷길이 여러 개일 수도 있다.

마지막 줄에 출발점 $A$와 도착점 $B$가 주어진다. ($1 \le A, B \le N$, $A \ne B$)

지용이가 A에서 B까지 안전하게 항해할 수 있으면 걸리는 최소 시간을, 그럴 수 없으면 -1을 출력한다.