Linee telefoniche#10153
Il fattore John vuole far arrivare una linea telefonica alla sua fattoria. Sfortunatamente, la compagnia telefonica non è molto disposta ad aiutarlo, quindi dovrà pagare parte dei cavi necessari per collegare la fattoria alla rete telefonica.
Nel territorio del fattore John sono sparsi pali telefonici solitari, numerati da a . Attualmente nessuno di essi è collegato con un cavo a un altro. In totale esistono coppie di pali che possono essere collegate con un cavo; le altre coppie si trovano troppo lontane l'una dall'altra.
L'-esimo cavo può collegare due pali distinti a_i e b_i e ha una lunghezza di l_i~(1 \le l_i \le 10^6) unità. Ogni coppia {a_i,b_i} compare nei dati di input al massimo una volta.
Il palo è già collegato alla rete telefonica, mentre il palo si trova presso la fattoria. I pali e devono essere collegati tramite un percorso composto da cavi; gli altri pali possono essere utilizzati oppure no.
La compagnia telefonica è disposta a fornire gratuitamente al fattore John tratti di cavo. Per ogni cavo oltre questi cavi gratuiti, il fattore deve pagare una somma pari alla lunghezza del più lungo tra i cavi rimanenti di cui ha bisogno, oppure se non gli servono cavi aggiuntivi.
Determinate la somma minima che il fattore John deve pagare.
Nella prima riga si trovano tre numeri interi e k~(1 \le n \le 1000, 1 \le p \le 10000, 0 \le k < n).
In ciascuna delle successive righe si trovano tre numeri interi a_i, b_i e l_i.
Stampate un singolo numero intero — la somma minima che il fattore John deve pagare. Se è impossibile collegare la fattoria alla rete telefonica, stampate .
Esempio 1