#include <bits/stdc++.h>
#include <set>
#include <list>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

set<int> ListaVecini[200010];

set< pair <int, pair<int, int> > > Muchii;

list< pair <int, int> > MuchiiArbore;

int n, m, frec[200010];

int Radacina(int nod){
    if(frec[nod] == nod) return nod;

    return Radacina(frec[nod]);
}

int main(){
    in >> n >> m;

    int x, y, cost;

    for(int i = 1; i <= m; i++){
        in >> x >> y >> cost;
        Muchii.insert( make_pair( cost, make_pair( x, y ) ));
    }

    set< pair<int, pair<int, int> > >::iterator it;

    /*for(it = Muchii.begin(); it != Muchii.end(); it++){
        cout << (*it).first << " " << (*it).second.first << " " << (*it).second.second << endl;
    }*/

    int costArbore = 0, nrMuchii = 0;

    for(int i  = 1; i <= n; i++) frec[i] = i;

    do{
        it = Muchii.begin();

        int Cost = (*it).first;
        int X = (*it).second.first;
        int Y = (*it).second.second;

        int rx = Radacina(X);
        int ry = Radacina(Y);



        if(rx != ry){

            nrMuchii++;
            costArbore += Cost;

            frec[rx] = ry;

            MuchiiArbore.push_back(make_pair(X, Y));

        }

        Muchii.erase(*it);

    }while(nrMuchii != n - 1);

    out << costArbore << endl;


    list< pair <int, int> >::iterator jt;

    out << MuchiiArbore.size() << endl;

    for(jt = MuchiiArbore.begin(); jt != MuchiiArbore.end(); jt++)
        out << (*jt).first << " " << (*jt).second << endl;
}