지각하면 안 돼

준하는 평범한 대학생이다. 이번 학기 수강신청을 완전히 망쳐서 시간표가 엉망이 되었고, 수업마다 옮겨 다녀야 하는 건물이 많다.

건물마다 이름이 있지만 매번 이름을 다 적기에는 잉크가 아까웠다. 그래서 옮겨 다닐 건물이 $N$개라면 편의상 1호관부터 $N$호관까지로 부르기로 했다.

건물이 많으니 지각도 잦았다. 지금 1호관에 있는 준하는 $N$호관에서 하는 이번 수업에 출석하지 못하면 F 학점을 받는다.

준하는 지각을 피하려고 택시를 자주 탔고, 건물 사이를 오가는 데 걸리는 시간과 택시비를 노트에 적어 두었다. 노트가 몇 장 없어서 이미 적어 둔 길은 다시 적지 않았다. 두 건물 사이에는 길이 하나뿐이라 같은 길을 다른 시간이나 다른 택시비로 적은 경우는 없다. 가는 길과 오는 길의 시간과 택시비도 같다.

학사경고가 걸린 급한 상황이라 노트에 없는 새로운 길로 가는 모험은 하지 않는다.

아래는 건물이 5개인 경우다.

1호관에서 듣던 수업이 끝나고 3시간 안에 5호관까지 가야 한다. 노트를 급히 펼쳐 봤지만 어떻게 가야 할지 모르겠다.

가진 돈은 4,000원뿐이고 남은 한 달을 이 돈으로 살아야 하니 지출을 최소로 줄이고 싶다.

이런 일이 앞으로도 자주 있을 테니 준하는 이번 수업을 포기하고 일반화된 프로그램을 만들어 달라고 부탁했다.

건물 사이의 이동 시간과 택시비, 지금 가진 돈이 주어질 때 $T$분 안에 최소 얼마의 지출로 도착할 수 있는지 출력하는 프로그램을 작성하자.

첫째 줄에 건물의 개수 $N$ ($2 \le N \le 100$)이 주어진다.

둘째 줄에 수업 출석까지 남은 시간 $T$ ($1 \le T \le 10000$, 단위는 분)와 현재 가지고 있는 돈 $M$ ($0 \le M \le 10000$)이 차례로 주어진다.

셋째 줄에 노트에 적혀 있는 건물 사이 길의 개수 $L$ ($1 \le L \le 10000$)이 주어진다.

다음 $L$개의 줄에는 길의 양 끝에 있는 두 건물의 번호와 그 길의 이동 시간(분), 택시비가 주어진다. 이동 시간과 택시비는 모두 10,000을 넘지 않는 자연수다. 양 끝에 있는 두 건물의 번호는 서로 다르다.

$T$분 안에 1번 건물에서 $N$번 건물까지 $M$원 이하의 지출로 갈 수 있으면 최소 지출액을 출력한다.

갈 수 없으면 -1을 출력한다.

위 그림에서 1호관을 출발해 3호관과 4호관을 거쳐 5호관으로 가면 3시간 만에 3,500원으로 도착할 수 있다. 다행히 이번 수업은 휴강이었다고 한다.