#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;
vector <int> Comp[200002];

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);
    }
    arbori = vector <int> (n + 1);
    for (int i = 1; i <= n; ++i)
        arbori[i] = i, Comp[i].push_back(i);
}

int main()
{
    citire();
    sort (muchii.begin(), muchii.end());

    for (int i = 0; i < m; i++)
    {
        if (arbori[muchii[i].nod1] != arbori[muchii[i].nod2])
        {
            int rad1 = arbori[muchii[i].nod1], rad2 = arbori[muchii[i].nod2];
            if (Comp[rad1].size() > Comp[rad2].size())
            {
                for (const int & x : Comp[rad2])
                {
                    Comp[rad1].push_back(x);
                    arbori[x] = rad1;
                }
                Comp[rad2].clear();
            }
            else
            {
                for (const int & x : Comp[rad1])
                {
                    Comp[rad2].push_back(x);
                    arbori[x] = rad2;
                }
                Comp[rad1].clear();
            }
            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;
}