Farmer John quer instalar uma linha telefônica em sua fazenda. Infelizmente, a companhia telefônica não coopera, então ele precisa pagar alguns dos cabos necessários para conectar a fazenda ao sistema telefônico.

Há $N$ postes telefônicos solitários, $(1 \le N \le 1,000)$, espalhados por sua propriedade e convenientemente numerados $1..N$; nenhum cabo os conecta. Um total de $P$ pares de postes, $(1 \le P \le 10,000)$, pode ser ligado por um cabo; os demais estão distantes demais.

O cabo $i$ pode conectar os postes distintos $A_i$ e $B_i$, com comprimento $L_i$ unidades se usado, $(1 \le L_i \le 1,000,000)$. Os dados de entrada nunca mencionam um par {$A_i,B_i$} mais de uma vez. O poste $1$ já está conectado ao sistema, e o poste $N$ fica na fazenda. Os postes $1$ e $N$ precisam ser ligados por um caminho de cabos; os outros postes podem ou não ser usados.

A companhia está disposta a fornecer gratuitamente $K$ cabos a Farmer John, $(0 \le K < N)$. Além disso, ele terá de pagar um preço igual ao comprimento do maior cabo restante de que precisa (cada par de postes é conectado por um cabo separado), ou $0$ se não precisar de cabos adicionais.

Determine o menor valor que Farmer John precisa pagar.

Entrada

Leia a entrada da entrada padrão.

• Linha 1: três inteiros separados por espaços: $N$, $P$ e $K$.

• Linhas $2..P+1$: a linha $i+1$ contém três inteiros separados por espaços: $A_i$, $B_i$ e $L_i$.

Saída

Escreva a resposta na saída padrão.

• Linha 1: um único inteiro, o menor valor que Farmer John pode pagar. Se for impossível conectar a fazenda à companhia, imprima $-1$.

Exemplos

Entrada 1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

Saída 1

4

Explicação

Há 5 postes. O poste $1$ não pode ser conectado diretamente aos postes $4$ ou $5$. O poste $5$ não pode ser conectado diretamente aos postes $1$ ou $3$. Todos os demais pares podem ser conectados. A companhia fornecerá um cabo gratuito.

Se o poste $1$ for conectado ao $3$, o $3$ ao $2$ e o $2$ ao $5$, Farmer John precisará de cabos de comprimentos $4$, $3$ e $9$. A companhia fornecerá o cabo de comprimento $9$, então o maior cabo ainda necessário tem comprimento $4$.

Autor do problema: Paul Christiano, 2007