택시!

면접 대비

시간 제한1초메모리 제한128 MB

요약

각 도로에 이동 시간과 요금이 있는 양방향 그래프에서, 총요금이 예산 r을 넘지 않으면서 출발점 s에서 도착점 d까지 가는 최소 총시간을 구한다.

난이도: 보통10점 중 6점
유형: 그래프, 최단 경로, 동적 계획법, 힙
정답자: 아직 제출이 없습니다

문제

택시 기사: "손님, 어디로 갈까요?"

승객: "케망기산의 비누스 캠퍼스로 가주세요."

택시 기사: "네, 어느 길로 갈까요?"

승객: "가장 빠른 길로 가주세요."

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

이 문제에서는 이러한 상황을 모형화합니다. 도시에는 $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$ 까지 가고자 한다는 뜻입니다.

출력

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

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

예제3

예제 1

입력

예상 출력

16
10

예제 2
입력
```
2 1
0 1 5 5
0 1 10
```
예상 출력
```
5
```
예제 3
입력
```
3 3
0 2 2 100
0 1 3 1
1 2 3 1
0 2 10
```
예상 출력
```
6
```