KCM Travel

Chanmin qualified for Google Code Jam World Finals, but Google pays at most $M$ for travel. Given flights with cost and duration between airports, find the minimum travel time from airport 1 (Incheon) to airport $N$ (LA) with total cost at most $M$. If impossible, print Poor KCM.

• Line 1: integer $T$ (always 1)
• Per test: integers $N$, $M$, $K$, then $K$ lines with $u$, $v$, $c$, $d$

For each test, print the minimum time, or Poor KCM if no route fits the budget.