KCM 여행

아직 제출이 없습니다시간 제한3초메모리 제한256 MB

문제 설명

예제3

문제

찬민이는 Google Code Jam World Finals에 초대받았지만, 구글이 여행비를 최대 $M$ 원까지만 지원한다. 공항 $1$ (인천)에서 공항 $N$ (LA)까지 총 비용이 $M$ 이하인 경로 중 소요시간이 최소인 것을 구하라. 도착할 수 없으면 Poor KCM을 출력한다.

입력

첫 줄: 테스트 케이스 수 $T$ (항상 1)
각 테스트: $N$ , $M$ , $K$ , 이어서 $K$ 개의 항공편 $u$ , $v$ , $c$ , $d$ ( $1 \leq u, v \leq N$ , $u \neq v$ )

출력

각 테스트마다 최소 소요시간 한 줄. 불가능하면 Poor KCM.