#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define MAX 100001

using namespace std;
ifstream fin ("apm.in");
ofstream fout("apm.out");



class Graf{
    public:
    //date membre
        vector <pair<pair<int, int>, int> > A;

        //nr muchii sol
        int msol;
        //muchiile solutie
        vector <pair<int, int> > sol;
        int mM, mN;
        vector<int> parent;
        vector<int> rank;
        //static bool viz[MAX];


        //constructor

        Graf(int N, int M){
            mN = N;
            mM = M;
            parent.resize(N+1);
            rank.resize(N+1);

        }

        void CitireG(int M);

        int Find(int x);
        void Union(int x, int y);
        void Kruskall();

};

bool ok(const pair<pair<int, int>, int>&x, const pair<pair<int, int>, int>&y){
    //comparam al 2 lea parametru din perechile de tipul ((x,y),c) - care reprezinta costul
    return (x.second < y.second);
}

void Graf:: CitireG(int M){

    int x,y,c;

    for(int i = 0; i < M; i++){

        fin >> x >> y >> c;
        A.push_back(make_pair(make_pair(x,y),c));
    }
}

int Graf :: Find(int x){
    //daca nu mai gasim tata pentru nodul curent
    if( x == parent[x])
        return x;

    //mergem din tata in tata pana gasim nodul de start
    return Find(parent[x]);
}

void Graf :: Union (int x, int y){
    //gasim radacina/stramosul fiecarei componente pe care vrem sa le unim
    int px = Find(x);
    int py = Find(y);

    if(rank[px] >= rank[py]){
            //parintele subarborelui mai mic devine subarborele mare (Radacina sa)

        parent[py] = px;
        rank[px] += rank[py];
        msol++;
    }
    else{

        parent[px] = py;
        rank[py] += rank[px];
        msol++;
    }
}

void Graf :: Kruskall(){

    int C = 0; //costul total
    int x,y;
    //momentan n avem nicio muchie solutie
    msol = 0;

    //initializam vectorii parent si rank
     for (int i = 1; i <= mN; i++)
        parent[i] = i, rank[i] = 1;


    //sortam vectorul de muchii crescator in fc de cost

    sort(A.begin(), A.end(), ok);

    //verificam muchiile pe rand
    for(int i = 0 ; i < mM; i++){

        //cautam "cel mai indepartat stramos" pentru ambele capete ale muchiei
        x = Find(A[i].first.first);
        y = Find(A[i].first.second);

        //daca nu au "stramos" comun, atunci nu exista alt drum de la x la y in afara de muchia x-y
        if(y != x){
            //o adaugam in vect de sol
            sol.push_back(make_pair(A[i].first.first, A[i].first.second));

            //si punem muchia pe graful nostru actual
            Union(A[i].first.first, A[i].first.second);

            //adunam costul muchiei la costul tota
            C+= A[i].second;
        }
    }

    fout << C << "\n";
    fout << msol <<"\n";

    for(int i = 0; i < msol; i++){
        fout << sol[i].first << " " << sol[i].second << "\n";

    }

}


int main(){
    int N, M;
    fin >> N >> M;
    Graf G(N,M);
    G.CitireG(M);

    G.Kruskall();


    return 0;
}