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

using namespace std;

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

struct muchie
{
    int nod1, nod2, cost;
};

vector<muchie> muchii, solutii;
vector<int> radaciniArbori, arbori[32005];

int n, m, costMinim;

void quickSort(vector<muchie> &v, int st, int dr)
{
    int i = st, j = dr;
    int pivot = v[(st + dr) / 2].cost;

    while (i <= j)
    {
        while(v[i].cost < pivot)
            i++;
        while(v[j].cost > pivot)
            j--;
        if (i <= j)
        {
            swap(v[i], v[j]);
            i++;
            j--;
        }
    }

    if (st < j)
        quickSort(v, st, j);
    if (i < dr)
        quickSort(v, i, dr);
}

void citire()
{
    fin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        muchie muchieCurenta;
        fin >> muchieCurenta.nod1 >> muchieCurenta.nod2 >> muchieCurenta.cost;
        muchii.push_back(muchieCurenta);
    }

    radaciniArbori = vector<int> (n + 1);

    for (int i = 1; i <= n; i++)
    {
        radaciniArbori[i] = i;
        arbori[i].push_back(i);
    }
}

int main()
{
    citire();
    quickSort(muchii, 0, muchii.size() - 1);

    for (int i = 0; i < m; i++)
    {
        if (radaciniArbori[muchii[i].nod1] != radaciniArbori[muchii[i].nod2])
        {
            int rad1 = radaciniArbori[muchii[i].nod1];
            int rad2 = radaciniArbori[muchii[i].nod2];

            if (arbori[rad1].size() < arbori[rad2].size())
            {
                for (int j = 0; j < arbori[rad1].size(); j++)
                {
                    int nodCurent = arbori[rad1][j];
                    arbori[rad2].push_back(nodCurent);
                    radaciniArbori[nodCurent] = rad2;
                }
            }
            else
            {
                for (int j = 0; j < arbori[rad2].size(); j++)
                {
                    int nodCurent = arbori[rad2][j];
                    arbori[rad1].push_back(nodCurent);
                    radaciniArbori[nodCurent] = rad1;
                }
            }

            costMinim += muchii[i].cost;

            solutii.push_back(muchii[i]);

//            for (int i = 0; i < n; i++)
//            {
//                fout << arbori[i] << " ";
//            }
//            fout << endl;
        }
    }

    fout << costMinim << "\n";
    fout << solutii.size() << "\n";
    for (int i = 0; i < solutii.size(); i++)
        fout << solutii[i].nod1 << " " << solutii[i].nod2 << "\n";

    return 0;
}