Farmer John veut installer une ligne téléphonique à sa ferme. Malheureusement, l’opérateur téléphonique n’est pas coopératif : il doit donc payer certains câbles nécessaires pour relier sa ferme au réseau.
$N$ poteaux téléphoniques isolés, $(1 \le N \le 1,000)$, sont dispersés sur sa propriété et numérotés commodément $1..N$ ; aucun câble ne les relie. Au total, $P$ paires de poteaux, $(1 \le P \le 10,000)$, peuvent être reliées par un câble ; les autres sont trop éloignées.
Le câble $i$ peut relier deux poteaux distincts $A_i$ et $B_i$ ; s’il est utilisé, sa longueur est $L_i$ unités, $(1 \le L_i \le 1,000,000)$. Les données d’entrée ne mentionnent jamais une même paire {$A_i,B_i$} plus d’une fois. Le poteau $1$ est déjà connecté au réseau, et le poteau $N$ est à la ferme. Les poteaux $1$ et $N$ doivent être reliés par un chemin de câbles ; les autres poteaux peuvent être utilisés ou non.
Il se trouve que l’opérateur accepte de fournir gratuitement $K$ câbles à Farmer John, $(0 \le K < N)$. Au-delà, il doit payer un prix égal à la longueur du plus long câble restant dont il a besoin (chaque paire de poteaux est reliée par un câble distinct), ou $0$ s’il n’a besoin d’aucun câble supplémentaire.
Déterminez la somme minimale que Farmer John doit payer.
Entrée
Lisez les données sur l’entrée standard.
Ligne 1 : trois entiers séparés par des espaces : $N$, $P$ et $K$.
Lignes $2..P+1$ : la ligne $i+1$ contient trois entiers séparés par des espaces : $A_i$, $B_i$ et $L_i$.
Sortie
Écrivez la réponse sur la sortie standard.
- Ligne 1 : un entier, la somme minimale que Farmer John peut payer. S’il est impossible de relier la ferme à l’opérateur, affichez $-1$.
Exemples
Entrée 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
Sortie 1
4
Remarque
Il y a 5 poteaux. Le poteau $1$ ne peut pas être relié directement aux poteaux $4$ ou $5$. Le poteau $5$ ne peut pas être relié directement aux poteaux $1$ ou $3$. Toutes les autres paires peuvent être reliées. L’opérateur fournira un câble gratuit.
Si le poteau $1$ est relié au poteau $3$, le poteau $3$ au poteau $2$, et le poteau $2$ au poteau $5$, Farmer John a besoin de câbles de longueurs $4$, $3$ et $9$. L’opérateur fournit le câble de longueur $9$, donc le plus long câble restant nécessaire mesure $4$.
Auteur du problème : Paul Christiano, 2007