// KRUSKAL -- O (mlogn)
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>

std::ifstream f("apm.in");
std::ofstream g("apm.out");

#define NMAX 200000 // constrangeri

/// structura => muchia (x,y) cu costul c
struct muchii
{
    int x, y, c;
};

// variabile globale
muchii v[NMAX + 1], apm[NMAX + 1];
int n, m, dim[NMAX + 1], tata[NMAX + 1];
int k = 0, rez = 0;

/// sortarea crescatoare dupa cost
inline bool cmp(const muchii &a, const muchii &b)
{
    return a.c < b.c;
}

/// returneaza tatal/radacina unei paduri
int rep(int x)
{
    if (x != tata[x])
        x = rep(tata[x]);
    return tata[x];
}

// union intre doua paduri in functie de rep

void uni(int x, int y)
{
    x = rep(x); // cauta tatii/radacinile ambelor multimi
    y = rep(y);

    // uneste padurea mai mica de padurea mai mare
    // tatal/radacina noii paduri = tatal/radacina padurii mai mare
    if (dim[y] > dim[x])
    {
        tata[x] = y;
        dim[y] += dim[x];
    }
    else
    {
        tata[y] = x;
        dim[x] += dim[y];
    }
}

// kruskal folosindu-ne de union/find

void kruskal()
{
    // initial, fiecare nod este o componenta conexa, izolata
    for (int i = 1; i <= n; i++)
    {
        dim[i] = 1;
        tata[i] = i;
    }

    // pentru fiecare muchie si cat timp nu au fost unite toate nodurile
    for (int i = 1; i <= m && k < n; i++)
    {
        // daca cele doua noduri din muchie nu formeaza o padure
        if (rep(v[i].x) != rep(v[i].y))
        {
            // unim padurile si
            uni(v[i].x, v[i].y);

            // se adauga costul muchiei la costul total
            rez += v[i].c;

            // se adauga muchia in arborele final
            apm[++k] = v[i];
        }
    }
}

int main()
{
    // citire date
    f >> n >> m;
    for (int i = 1; i <= m; i++)
        f >> v[i].x >> v[i].y >> v[i].c;

    // sortare muchii dupa cost
    std::sort(v + 1, v + m + 1, cmp);

    // facem kruskal 
    kruskal();

    // afisare rezultat
    g<<rez<<'\n'<<k<<'\n';
    for (int i=1;i<=k;i++) 
        g<<apm[i].x<<' '<<apm[i].y<<'\n';
}