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

using namespace std;

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

#define MMAX 400005
#define NMAX 200005

struct muchie{
    int i, j, cost;
};

int n, m, t[NMAX], s, nr_muchii;
muchie x[MMAX];

bool cmp (muchie a, muchie b)
{
    if(a.cost==b.cost)
        return a.i<=b.i;
    return a.cost<b.cost;
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>x[i].i>>x[i].j>>x[i].cost;
    sort(x+1, x+m+1, cmp);

    ///Initializare reprezentanti subarbori
    for(int i=1; i<=n; i++)
        t[i]=i;

    ///Determinare APM
    for(int i=1; i<=m; i++)
    {
        if(t[x[i].i]!=t[x[i].j]) ///extremitatile fac parte din subarbori diferiti
        {
            s+=x[i].cost;
            x[i].cost=-1001;
            nr_muchii++;
            ///reunim subarborii
            int ti=t[x[i].i], tj=t[x[i].j];
            for(int j=1; j<=n; j++)
                if(t[j]==tj)
                    t[j]=ti;
        }
    }
    fout<<s<<"\n";
    fout<<nr_muchii<<"\n";
    for(int i=1; i<=m; i++)
        if(x[i].cost==-1001)
            fout<<x[i].i<<" "<<x[i].j<<"\n";
    return 0;
}