#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200001

using namespace std;

struct muchie {
    int from,to;
    int cost;
};

typedef vector<muchie> adiacente;
adiacente toateMuchiile;
adiacente rezultat;

int n, m, tata[NMAX], pondereArbore;

void kruskal();

bool sortare(muchie a,muchie b){
    return (a.cost<b.cost);
}

int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    int x, y, c;
    for (int i = 1; i <= m; ++i)
    {
        f>>x>>y>>c;
        muchie X;
        X.from = x;
        X.to = y;
        X.cost = c;
        toateMuchiile.push_back(X);
    }

    kruskal();

    g<<pondereArbore<<'\n';
    g<<rezultat.size()<<'\n';
    for (adiacente::iterator i = rezultat.begin(); i != rezultat.end(); ++i)
        g<<i->to<<' '<<i->from<<'\n';

    return 0;
}


int set(int nod) {
    if (tata[nod] == 0)
        return nod;
    tata[nod] = set(tata[nod]);
    return tata[nod];
}

void kruskal() {
    sort(toateMuchiile.begin(), toateMuchiile.end(), sortare);
    for (adiacente::iterator i = toateMuchiile.begin(); i != toateMuchiile.end()-1; ++i) {
        if (set(i->from) != set(i->to)) {
            pondereArbore += i->cost;
            tata[set(i->from)] = set(i->to);
            rezultat.push_back(*i);
            if(rezultat.size()==n-1)
                break;
        }
    }
}