/**
 * Autore:      VANESSA VIDALI - VR379624
 * Data:        11/02/2015
 * Problema:    Esercizio 1 - MST
 **/

#include<cstdio>
#include <vector>
#include <fstream>
#include <iostream>
#include <cassert>
#include <algorithm>

using namespace std;

/** PSEUDO-ALGORITMO *
 *
 *  1) ordino archi per pesi crescenti
 *  2) per ogni arco, ordino nodi in ordine crescente (trasformo il grafo in un grafo orientato)
 *  3) inizializzo peso w=0, insieme MST vuoto
 *  4) scorro la lista degli archi in ordine crescente
 *   4.1) il nodo di arrivo dell'arco è contenuto in MST?
 *     4.1.1) SI, skip
 *     4.1.2) NO, aggiungo l'arco in MST e aggiungo il peso in w
 *  5) ritorno MST e w
 *
 */

/* struttura arco */
struct arco {
    int nodoPartenza;
    int nodoArrivo;
    int peso;
    bool soluzioneOttima;
};

const int MAX_N = 10000; int N;
const int MAX_M = 1000000; int M;
const int MAX_Q = 100; int Q;
int pesoMinimo = 0;
vector<arco> grafoIniziale; //Grafo originale
vector<arco> MST; //Grafo finale MST

/* Criterio del sort */
bool comparaPesi(arco a, arco b){
    return a.peso<b.peso;
}


/* Guardo se il nodo di arrivo dell'arco è contenuto in MST */
bool contenutoInMST(arco t){ //t arco target

    for(int i = 0; i < (int) MST.size(); i++){
        if( ((arco)MST.at(i)).nodoArrivo == t.nodoArrivo){
            return true;
        }
    }
    return false;
}

/*Algoritmo*/
void algoritmoMST(){



    /*ordino nodi degli archi*/
    for(int i = 0; i < (int) grafoIniziale.size(); i++){
        cout << ((arco)grafoIniziale.at(i)).peso << " " << ((arco)grafoIniziale.at(i)).nodoPartenza << " " << ((arco)grafoIniziale.at(i)).nodoArrivo << "\n";
    }

    /*ordino grafo per pesi crescenti*/
    sort(grafoIniziale.begin(), grafoIniziale.end(), comparaPesi);

    /* MST */
    for(int i = 0; i < (int) grafoIniziale.size(); i++){
        if(!contenutoInMST((arco) grafoIniziale.at(i))){
            pesoMinimo = pesoMinimo + (((arco) grafoIniziale.at(i)).peso);
            MST.push_back(((arco)grafoIniziale.at(i)));
        }
    }
}

int main(int argc, char** argv){
    /*Leggo input da file*/
    ifstream fin("input.txt"); assert(fin);
    fin >> N >> M >> Q;
    for(int i=0; i<M; i++){
        int a,b,w;
        fin >> a >> b >> w;
        if(a>b){
            int tmp=b;
            b=a;
            a=tmp;
        }
        arco m = {a,b,w,false};
        if(i<Q)
            m.soluzioneOttima=true;
        grafoIniziale.push_back(m);
    }
    fin.close();

    /* Algoritmo */
    algoritmoMST();



    /*Scrivo output su file*/
    ofstream fout("output.txt"); assert(fout);
    fout << pesoMinimo;
    fout.close();
    return 0;
}