#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> arbori;

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);
    }

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

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

    for (int i = 0; i < m; i++)
    {
        if (arbori[muchii[i].nod1 - 1] != arbori[muchii[i].nod2 - 1])
        {
            int val = arbori[muchii[i].nod2 - 1];

            for (int j = 0; j < n; j++)
            {
                if (arbori[j] == val)
                    arbori[j] = arbori[muchii[i].nod1 - 1];
            }

            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;
}