올림픽

툼볼리아는 남아메리카의 동쪽(또는 동아메리카의 남쪽)에 있는 작은 나라다. 이번에 역사상 처음으로 올림픽에 선수단을 보낸다. 베이징에 모일 선수가 만 명을 넘는다는 공식 추산에 비하면 툼볼리아 선수단은 아주 작지만, 이번 참가는 나라의 이미지와 관광에 큰 의미가 있다.

선수 선발을 마친 툼볼리아 올림픽 위원회는 이제 선수들의 항공권을 사야 한다. 위원회는 비용을 아끼려고 에어록 항공권만 사기로 했다. 그런데 대회를 보러 가려는 툼볼리아 사람이 많아서 에어록의 좌석은 이미 상당수 팔렸다. 그래서 위원회는 각 항공편에 남은 빈 좌석 수만큼만 표를 살 수 있다.

에어록의 모든 항공편은 매일 정오 전에 출발해 정오 후에 도착한다. 그래서 한 선수는 하루에 비행기를 한 번만 탈 수 있다. 에어록은 자사가 운항하는 모든 항공편과 각 항공편의 빈 좌석 수를 정리한 목록을 위원회에 넘겼다. 같은 구간의 빈 좌석 수는 날마다 똑같다. 선수는 어느 공항에서든 며칠이든 머물다가 다음 항공편을 탈 수 있다.

에어록 항공편만으로 툼볼리아에서 베이징까지 갈 수 있다는 사실은 위원회가 이미 확인했다. 그래도 일정을 짜기가 쉽지 않아, 위원회는 항공편 목록을 읽어 선수단 전원이 베이징에 도착하는 데 필요한 최소 일수를 구하는 프로그램을 요청했다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$, $M$, $A$가 주어진다. $N$은 에어록이 취항하는 공항의 수($2 \le N \le 50$), $M$은 빈 좌석이 남은 항공편의 수($1 \le M \le 2450$), $A$는 툼볼리아 선수단의 선수 수($1 \le A \le 50$)다.

이어지는 $M$개의 줄에는 항공편 하나의 정보가 정수 $O$, $D$, $S$로 주어진다. $O$는 출발 공항($1 \le O \le N$), $D$는 도착 공항($1 \le D \le N$, $O \ne D$), $S$는 그 항공편의 빈 좌석 수($1 \le S \le 50$)다. 공항은 1번부터 $N$번까지 번호가 붙어 있고, 툼볼리아 국제공항이 1번, 베이징 국제공항이 $N$번이다.

$X$에서 $Y$로 가는 항공편이 있어도 $Y$에서 $X$로 가는 항공편이 있다는 보장은 없다. 다만 한 공항에서 다른 공항으로 가는 항공편은 방향마다 최대 하나다. 1번 공항에서 $N$번 공항으로 가는 경로는 항상 존재한다.

입력의 끝은 $N = M = A = 0$인 줄로 표시된다. 이 줄은 처리하지 않는다.

각 테스트 케이스마다 툼볼리아 선수 전원이 베이징에 도착하는 데 필요한 최소 일수를 정수 하나로 한 줄에 출력한다. 첫 항공편이 출발하는 날을 1일로 세고, 마지막 선수가 도착하는 날이 답이다. 선수마다 도착하는 날이 달라도 되고, 출발한 순서대로 도착하지 않아도 된다.