Farmer John verifica diligentemente as vacas todos os dias. Ele percorre algumas das $M$ $(1 \le M \le 50,000)$ trilhas, numeradas $1,\ldots,M$, desde o pasto $1$ até o pasto $N$ (uma viagem sempre possível nos mapas de trilhas dos dados de teste). Os $N$ $(1 \le N \le 10,000)$ pastos da fazenda de Farmer John, numerados $1,\ldots,N$, estão atualmente ligados por trilhas de terra bidirecionais. Cada trilha $i$ liga os pastos $P1_{i}$ e $P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$ e exige $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ unidades de tempo para ser percorrida.

Ele quer renovar algumas trilhas da fazenda para economizar tempo em sua longa viagem. Especificamente, escolherá $K$ $(1 \le K \le 20)$ trilhas para transformá-las em rodovias, reduzindo efetivamente o tempo de percurso de cada uma a $0$. Ajude FJ a decidir quais trilhas renovar para minimizar o tempo necessário para ir do pasto $1$ ao $N$.

Entrada

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

• Linhas $2,\ldots,M+1$: a linha $i+1$ descreve a trilha $i$ com três inteiros separados por espaços: $P1_{i}$, $P2_{i}$ e $T_{i}$.

Saída

• Linha 1: o comprimento do caminho mais curto após renovar no máximo $K$ arestas.

Exemplos

Entrada 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Saída 1

1

Explicação

$K$ é $1$; renove a trilha $3->4$ para que leve $0$ em vez de $100$. O novo caminho mais curto é $1->3->4$, e o tempo total de percurso agora é $1$.

Autor do problema: Percy Liang, 2008