Farmer John surveille consciencieusement ses vaches chaque jour. Il emprunte certains des $M$ $(1 \le M \le 50,000)$ sentiers, numérotés $1,\ldots,M$, pour aller du pâturage $1$ jusqu’au pâturage $N$ (un trajet toujours possible pour les cartes de sentiers des données de test). Les $N$ $(1 \le N \le 10,000)$ pâturages de la ferme de Farmer John, numérotés $1,\ldots,N$, sont actuellement reliés par des sentiers de terre bidirectionnels. Chaque sentier $i$ relie les pâturages $P1_{i}$ et $P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$ et demande $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ unités de temps pour être parcouru.

Il veut rénover certains sentiers de sa ferme afin de gagner du temps lors de son long trajet. Plus précisément, il choisira $K$ $(1 \le K \le 20)$ sentiers à transformer en grandes routes, ce qui ramènera effectivement leur temps de parcours à $0$. Aidez FJ à choisir les sentiers à rénover pour minimiser le temps nécessaire pour aller du pâturage $1$ à $N$.

Entrée

• Ligne 1 : trois entiers séparés par des espaces : $N$, $M$ et $K$.

• Lignes $2,\ldots,M+1$ : la ligne $i+1$ décrit le sentier $i$ par trois entiers séparés par des espaces : $P1_{i}$, $P2_{i}$ et $T_{i}$.

Sortie

• Ligne 1 : la longueur du plus court chemin après rénovation d’au plus $K$ arêtes.

Exemples

Entrée 1

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

Sortie 1

1

Remarque

$K$ vaut $1$ ; rénovez le sentier $3->4$ pour passer d’un temps de $100$ à $0$. Le nouveau plus court chemin est $1->3->4$, et le temps total de parcours vaut maintenant $1$.

Auteur du problème : Percy Liang, 2008