#include <fstream>
#include <algorithm>
#include <vector>
#define INF 1000000000

using namespace std;

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

struct muchie
{
    int x;
    int y;
    int cost;
}v[400010];

int n,m,i,j,t[200010],s[200010],l,sol;

int cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

int rad(int x)
{
    while (t[x] > 0)
        x = t[x];
    ///compresia drumului:
    /*
        int y = x, aux;
        while (t[y] > 0)
        {
            aux = t[y];
            t[y] = x;
            y = aux;
        }
    */
    return x;
}

int main()
{
    fin >> n >> m;
    ///kruskal: apm prin selectie de muchii
    ///se sorteaza crescator dupa cost muchiile si se fac n-1 alegeri
    ///de muchii, in ordine crescatoare a costurilor si la fiecare pas
    ///muchia aleasa sa aiba extremitatile in componente conexe diferite
    ///dupa alegere, componentele conexe se unesc
    for (i=1; i<=m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;
    sort(v+1, v+m+1, cmp);
    ///consider ca fiecare nod este o componenta conexa diferita
    for (i=1; i<=n; i++)
        t[i] = -1;
    ///aleg muchiile in ordine crescatoare a costului
    for (i=1; i<=m; i++)
    {
        int rx = rad(v[i].x);
        int ry = rad(v[i].y);
        if (rx != ry)
        {
            s[++l] = i;
            sol += v[i].cost;
            ///tin minte cu - cate noduri are arborele
            ///unesc la arborele cu mai multe noduri
            if (t[rx] < t[ry])
            {
                t[rx] += t[ry];
                t[ry] = rx;
            }
            else
            {
                t[ry] += t[rx];
                t[rx] = ry;
            }
        }
    }
    fout << sol << "\n" << n-1 << "\n";
    for (i=1; i<n; i++)
        fout << v[s[i]].x << " " << v[s[i]].y << "\n";
    return 0;
}