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

using namespace std;

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

struct muchie
{
    int nod1, nod2, cost;

    bool operator < (const muchie & A) const
    {
        return cost < A.cost;
    }
};

vector<muchie> muchii, solutii;
vector<int> arbori;

int n, m, costMinim;

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();
    sort (muchii.begin(), muchii.end());

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

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