#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct muchie{int x,y,c;};
vector<int> tata;

bool comparator(muchie a, muchie b)
{
    return a.c<b.c;
}

int radacina(int nod)
{
    if(tata[nod] != nod)
        return radacina(tata[nod]);
    return nod;
}

int main(){
    int N,M;
    vector<muchie> muchii;

    // CITIRE
    ifstream f("apm.in");

    f>>N>>M;
    muchii.resize(M);

    for(int i = 0; i < M; i++)
        f>>muchii[i].x>>muchii[i].y>>muchii[i].c;

    f.close();

    // SORTAM MUCHIILE
    sort(muchii.begin(), muchii.end(), comparator);

    // FORMAM VECTORUL DE TATI
    tata.resize(N+1);
    for(int i = 1; i <= N; i++)
        tata[i] = i;

    vector<muchie> rezultat;
    for(int i = 0; i < muchii.size(); i++)
        // DACA NU FORMEAZA UN CICLU
        if(radacina(muchii[i].x) != radacina(muchii[i].y))
        {
            rezultat.push_back(muchii[i]);
            tata[radacina(muchii[i].y)] = radacina(muchii[i].x);
        }

    ofstream g("apm.out");

    int suma = 0;
    for(int i = 0; i < rezultat.size(); i++)
        suma += rezultat[i].c;
    g<<suma<<endl;

    g<<rezultat.size()<<endl;

    for(int i = 0; i < rezultat.size(); i++)
        g<<rezultat[i].x<<' '<<rezultat[i].y<<endl;

    g.close();
    return 0;
}