Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 20 de Dezembro
(o problema continuará depois disponível para submissão, mas sem contar para a nota)

[DAA 036] Trânsito complicado
(este problema é essencialmente o mesmo que criei para um CIIC, o concurso ibero-americano de informática e computação)

Um dos maiores problemas da cidade onde Rafael vive é o complicado trânsito automóvel. Todos os dias ele vai de casa para o trabalho em plena hora de ponta e muito tempo é passado completamente parado no trânsito, algo que o irrita profundamente. Rafael decide por isso planear cuidadosamente o melhor caminho a seguir.

Os anos acumulados a conduzir na cidade permitiram-lhe fazer uma mapa detalhado com informações sobre o trânsito. Para simplificar, Rafael decidiu numerar os vários locais da cidade com números de 0 a N-1, sendo que a sua casa está sempre no local 0 e o trabalho no local N-1. O mapa define estradas entre pares de locais, indicando a respetiva velocidade média de circulação automóvel. Nota que todas as estradas permitem a circulação em ambos os sentidos. Dado um caminho, o seu valor final é igual à menor velocidade média de uma das suas estradas constituintes.

A figura seguinte ilustra um caminho entre 0 (casa) e 8 (trabalho). Este caminho percorre os locais 0, 2, 4, 6 e 8, por esta ordem, e tem um valor de 22 Km/h, o mínimo das velocidades médias das suas estradas, que são 40, 22, 28 e 50.

É no entanto possível fazer melhor se seguirmos o caminho indicado pela próxima figura, que tem um valor de 32 Km/h, superior ao caminho anterior:

O Rafael sabe que que o presidente da câmara municipal tem disponível dinheiro para renovar algumas estradas. Uma estrada renovada transforma-se numa avenida com duas vias de circulação em cada sentido, o que duplica o valor da sua velocidade média. Por exemplo, caso fosse renovada a estrada entre os locais 2 e 3, a sua velocidade média passava a 48 Km/h, e o seguinte caminho de valor 35 Km/h (melhor que os anteriores) passava a ser possível:

Na realidade, a câmara terá dinheiro para renovar no máximo K estradas. Como o Rafael acha que sem dúvida o caminho que ele faz é muito importante, decide enviar à câmara uma carta explicando quais as estradas que deveriam ser renovadas para lhe permitir ter o melhor caminho possível. Por exemplo, se K fosse 1, o cenário explicado na figura anterior era o melhor que se poderia obter. Caso K seja 2, já não é assim. Neste caso, o melhor que se pode fazer é renovar as estradas entre 2 e 4, e entre 4 e 6, o que lhe permitiria fazer um caminho de valor 40 Km/h, tal como ilustrado na figura seguinte:

E para um caso geral? Quais seriam as estradas a renovar de modo a conseguir o melhor caminho possível para o Rafael?

O Problema

Dada um mapa com N locais, um conjunto de E estradas, com velocidades médias de circulação entre A e B iguais a V_A,B e um número K que indica o número de estradas que é possível renovar (duplicando a velocidade média), a tua tarefa é calcular qual o valor do melhor caminho possível de obter para ir do local 0 (a casa) até N-1 (o trabalho), depois de serem feitas um máximo de K renovações.

Input

A primeira linha do input contém um único inteiro N, o número de locais. A segunda linha contem um único inteiro E, o número de estradas existentes.

Seguem-se E linhas, cada uma contendo três inteiros A B V_A,B, separados por um único espaço, indicando que existe uma estrada entre A e B com velocidade média V_A,B. As estradas podem vir por qualquer ordem e nunca existem duas estradas diferentes entre o mesmo par de locais. Não podem existir estradas diretas de uma posição para si própria e existe sempre pelo menos um caminho entre 0 e N-1.

Finalmente, na linha seguinte, vem um único inteiro K, indicando o número de estradas que se pode renovar.

Output

O output deve ser constituído por uma linha contendo um único número inteiro representando o valor do melhor caminho possível de obter fazendo no máximo K renovações.

O valor de um caminho é igual à mínima velocidade média de uma das suas estradas constituintes. O melhor caminho é aquele que apresenta o maior valor possível. Nota que podes escolher fazer as renovações que dão origem ao melhor caminho e que uma estrada só pode ser renovada uma única vez. Se K for zero, então o resultado corresponde ao melhor caminho sem nenhuma renovação de estrada.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, acontece sempre que N≤10, E≤40 e K≤1.

9
11
0 2 40
2 4 22
4 6 28
6 8 50
0 1 32
1 3 32
3 5 43
5 7 35
7 8 47
2 3 24
4 5 21
1

35

9
11
0 2 40
2 4 22
4 6 28
6 8 50
0 1 32
1 3 32
3 5 43
5 7 35
7 8 47
2 3 24
4 5 21
2

40

Desenho e Análise de Algoritmos (CC2001)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto