택시!

• 택시 기사: "손님, 어디로 갈까요?"
• 승객: "케망기산의 비누스 캠퍼스로 가주세요."
• 택시 기사: "네, 어느 길로 갈까요?"
• 승객: "가장 빠른 길로 가주세요."

택시를 탈 때 흔히 나누는 대화입니다. 많은 사람들은 가장 빠른 길이 곧 가장 저렴한 길이라고 생각하지만, 항상 그렇지는 않습니다. 통행료가 있거나, 정체가 없는 대신 더 멀리 돌아가는 도로처럼 여러 요인 때문에 빠른 길이 오히려 더 비쌀 수도 있고, 그 반대일 수도 있습니다.

이 문제에서는 이러한 상황을 모형화합니다. 도시에는 $n$개의 교차로와, 교차로 쌍을 잇는 $m$개의 양방향 도로가 있습니다. 각 도로를 지날 때는 일정한 시간과 요금(택시비)이 듭니다. 가진 돈을 초과하지 않으면서 목적지까지 가는 데 걸리는 최소 시간을 구하는 프로그램을 작성하세요.

입력은 여러 개의 테스트 케이스로 이루어지며, 입력이 끝날 때까지 각 케이스를 순서대로 처리합니다.

각 케이스의 첫 줄에는 두 정수 $n$($1 \le n \le 100$, 교차로의 수)과 $m$(도로의 수)이 주어집니다. 교차로는 $0$번부터 $n-1$번까지 번호가 매겨져 있습니다.

이어지는 $m$개의 줄에는 각각 네 정수 $u$, $v$, $t$, $c$($1 \le t, c \le 100$)가 주어집니다. 이는 교차로 $u$와 $v$를 잇는 양방향 도로가 있으며, 이 도로를 지나는 데 $t$분과 $c$루피아가 든다는 뜻입니다.

각 케이스의 마지막 줄에는 세 정수 $s$, $d$, $r$($1 \le r \le 100$)가 주어집니다. 이는 가진 돈 $r$루피아만으로 출발지 $s$에서 목적지 $d$까지 가고자 한다는 뜻입니다.

각 케이스마다, 총 비용이 가진 돈을 넘지 않으면서 목적지에 도착하는 데 걸리는 최소 시간을 한 줄에 출력합니다.

각 케이스에서 목적지는 주어진 예산 안에서 항상 도달할 수 있음이 보장됩니다.