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

using namespace std;

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

class Graf
{
private:

    int numar_noduri, numar_muchii;
    int noduri1[1000], noduri2[1000];
    struct componente_muchie
    {
        int capat_stang, capat_drept, cost;
    };
    vector <componente_muchie> muchii;

public:

    void citire();
    void apm();
    int gasire(int);
    void unire(int, int);
};

void Graf :: citire()
{
    int capat_stang, capat_drept, cost;

    fin >> numar_noduri >> numar_muchii;

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> capat_stang >> capat_drept >> cost;
        muchii.push_back({capat_stang, capat_drept, cost});
    }
}

int Graf :: gasire(int a)
{
    int aux = a, aux2;

    while(noduri1[aux] != aux)
    {
        aux = noduri1[aux];
    }

    while(a != aux)
    {
        aux2 = noduri1[a];
        noduri1[a] = aux;
        a = aux2;
    }

    return a;
}

void Graf :: unire(int a, int b)
{
    a = gasire(a);
    b = gasire(b);

    if(noduri2[a] < noduri2[b])
        noduri1[a] = b;
    else
    {
        noduri1[b] = a;
        if(noduri2[a] == noduri2[b]) noduri2[a]++;
    }
}

void Graf :: apm()
{
    int numar_muchii_selectate = 0;
    int cost_minim = 0;

    for(int i = 1; i <= numar_noduri; i++)
        noduri1[i] = i;

    sort(muchii.begin(), muchii.end(), [](const componente_muchie &x, const componente_muchie &y) {return x.cost < y.cost;});

    vector <pair <int, int>> rezultat;

    for(const componente_muchie& x : muchii)
    {
        if(numar_muchii_selectate == numar_noduri - 1)
            break;

        if(gasire(x.capat_stang) == gasire(x.capat_drept))
            continue;

        numar_muchii_selectate++;
        cost_minim += x.cost;

        unire(x.capat_stang, x.capat_drept);
        rezultat.push_back({x.capat_stang, x.capat_drept});
    }

    fout << cost_minim << '\n';
    fout << rezultat.size() << '\n';

    for(auto x : rezultat)
        fout << x.second << " " << x.first << '\n';
}

int main()
{
    Graf x;
    x.citire();
    x.apm();

    return 0;
}