SPOJ Brasil

Tumbólia é um pequeno país ao leste da América do Sul (ou ao sul da América do Leste) que irá participar dos Jogos Olímpicos pela primeira vez na sua história. Apesar de sua delegação ser muito pequena comparada ao total de atletas que estarão em Pequim (as estimativas oficiais são de mais de dez mil atletas), a participação será fundamental para a imagem e para o turismo de Tumbólia.

Após selecionar os atletas, o Comitê Olímpico Tumboliano (COT) precisa comprar as pas- sagens para eles. A fim de economizar dinheiro, o COT decidiu comprar apenas passagens da Air Rock. No entanto, muitas das passagens da Air Rock já foram vendidas, uma vez que muitos tumbolianos desejam assistir aos Jogos. Sendo assim, o COT deverá comprar passagens de acordo com os assentos vagos em cada vôo.

Todos os vôos da Air Rock partem diariamente antes do meio-dia e chegam após o meio- dia; por isso, um atleta pode tomar apenas um avião por dia. A Air Rock providenciou uma lista contendo todos os vôos operados por ela e o número de assentos vagos em cada um (curiosamente, o número de assentos livres em um mesmo trecho é igual todos os dias).

O COT verificou que realmente é possível ir de Tumbólia para Pequim usando apenas vôos da Air Rock mas, mesmo assim, o COT está tendo dificuldades para planejar a viagem de seus atletas. Por isso, o COT pediu para você escrever um programa que, dada a lista de vôos da Air Rock, determina a menor quantidade de dias necessária para que todos os atletas cheguem em Pequim.

Entrada

A entrada contém vários casos de teste. A primeira linha de cada caso de teste contém três inteiros N, M e A indicando respectivamente a quantidade de aeroportos em que a Air Rock opera (2 ≤ N ≤ 50), a quantidade de vôos em que há assentos vagos (1 ≤ M ≤ 2.450) e quantos atletas a delegação tumboliana tem (1 ≤ A ≤ 50).

Cada uma das M linhas seguintes contém uma descrição de vôo com três inteiros O, D e S que indicam respectivamente o aeroporto de origem (1 ≤ O ≤ N), o aeroporto de destino (1 ≤ D ≤ N e O ≠ D) e a quantidade de assentos vagos naquele vôo (1 ≤ S ≤ 50). Os aeroportos são numerados de 1 a N; o Aeroporto Internacional de Tumbólia é o aeroporto 1, e o Aeroporto Internacional de Pequim é o aeroporto N.

A existência de um vôo de A para B não implica a existência de um vôo de B para A (mas sempre há no máximo um vôo de um aeroporto para outro em cada direção).

O final da entrada é indicado por N = M = A = 0.

A entrada deve ser lida da entrada padrão.

Saída

Para cada caso de teste da entrada seu programa deve produzir uma linha na saída contendo um inteiro, indicando a quantidade mínima de dias necessária para que todos os atletas tumbolianos cheguem em Pequim (alguns atletas podem chegar depois de outros, e eles não precisam chegar na mesma ordem em que partiram).

A saída deve ser escrita na saída padrão.

Exemplo

Entrada:
3 3 3
1 2 2
2 3 2
1 3 1
3 3 5
1 2 1
2 3 5
3 1 4
4 4 4
1 4 1
1 2 1
2 3 1
3 4 1
0 0 0

Saída:
2
6
3