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

using namespace std;

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

struct q
{
    int n1, n2, c;
};

q v[400005],  sol[200005];
int sef[200005];

int sef_suprem(int nod)
{
    if(sef[nod]==nod)
    {
        return nod;
    }
    return sef[nod]=sef_suprem(sef[nod]);
}

void unire(int x, int y)
{
    int sefx=sef_suprem(x);
    int sefy=sef_suprem(y);
    sef[sefx]=sefy;
}

int cmp(q a, q b)
{
    return a.c<b.c;
}

int main()
{
    int n, m;
    fin>>n>>m;

    for(int i=1; i<=n; i++)
    {
        sef[i]=i;
    }

    for(int i=1; i<=m; i++)
    {
        fin>>v[i].n1>>v[i].n2>>v[i].c;
    }

    sort(v+1,v+m+1,cmp);

    int cost=0, cnt=0;

    for(int i=1; i<=m; i++)
    {
        if(sef_suprem(v[i].n1)!=sef_suprem(v[i].n2))
        {
            unire(v[i].n1, v[i].n2);
            cost=cost+v[i].c;
            sol[++cnt]=v[i];
        }
    }

    fout<<cost<<"\n"<<cnt<<"\n";

    for(int i=1; i<=cnt; i++)
    {
        fout<<sol[i].n2<<" "<<sol[i].n1<<"\n";
    }
    return 0;
}