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

using namespace std;

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

const int nmax = 200000;
int n, m, costAPM, tata[nmax + 1], inaltime[nmax + 1];

pair<int, pair<int, int>> muchii[400001];

vector<int> muchiiSolutie;

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

    for(int i = 0; i < m; i++)
    {
        int x, y, z;

        fin >> x >> y >> z;

        muchii[i] = make_pair(z, make_pair(x, y));
    }
}

void sortareMuchii()
{
    sort(muchii, muchii + m);
}

void initializareAux()
{
    for(int i = 1; i <= n; i++)
        tata[i] = inaltime[i] = 0;
}

int reprezentant(int nod)
{
    if(tata[nod] == 0)
        return nod;

    tata[nod] = reprezentant(tata[nod]);

    return tata[nod];
}

void uneste(int nod1, int nod2)
{
    int rep_nod1, rep_nod2;

    rep_nod1 = reprezentant(nod1);
    rep_nod2 = reprezentant(nod2);

    if(inaltime[rep_nod1] > inaltime[rep_nod2])
        tata[rep_nod2] = rep_nod1;
    else
    {
        tata[rep_nod1] = rep_nod2;

        if(inaltime[rep_nod1] == inaltime[rep_nod2])
            inaltime[rep_nod2] += 1;
    }
}

int kruskal()
{
    int costTotal = 0;

    for(int i = 0; i < m; i++)
    {
        int nod1, nod2, cost;

        nod1 = muchii[i].second.first;
        nod2 = muchii[i].second.second;
        cost = muchii[i].first;

        if (reprezentant(nod1) != reprezentant(nod2))
        {
            costTotal += cost;
            muchiiSolutie.push_back(nod1);
            muchiiSolutie.push_back(nod2);
            uneste(nod1, nod2);
        }
    }

    return costTotal;
}

void afisareSolutie()
{
    fout << costAPM << endl << muchiiSolutie.size() / 2 << endl;

    for(int i = 0; i < muchiiSolutie.size(); i+= 2)
        fout << muchiiSolutie[i] << " " << muchiiSolutie[i + 1] << endl;
}

int main()
{

    citireGraf();

    initializareAux();

    sortareMuchii();

    costAPM = kruskal();

    afisareSolutie();


    fin.close();
    fout.close();

    return 0;
}