#include <fstream>
#include <algorithm>
using namespace std;

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


struct muchie
{
    int x,y,c;
};

bool cmp(muchie a, muchie b)
{
    return a.c<b.c;
}

const int N=200006;
muchie v[2*N];
int p[N],t[N];
muchie sol[N];

void reu(int x, int y)
{
    if(p[x]>p[y])
    {
        t[y]=x;
        p[x]+=p[y];
    }
    else
    {
        t[x]=y;
        p[y]+=p[x];
    }
}

int rad(int x)
{
    int r,y;
    r=x;
    while(t[r]!=r)
        r=t[r];
    while(t[x]!=x)
    {
        y=t[x];
        t[x]=r;
        x=t[x];
    }
    return r;
}
int main()
{
    int i,x,y,apm=0,m,n,nr=0;
    in>>n>>m;
    for(i=1;i<=m;i++)
        in>>v[i].x>>v[i].y>>v[i].c;

    sort(&v[1],&v[m+1],cmp);

    for(i=1;i<=n;i++)
    {
        p[i]=1;
        t[i]=i;
    }

    for(i=1;i<=m;i++)
    {
        x=rad(v[i].x);
        y=rad(v[i].y);
        if(x!=y)
        {
            apm+=v[i].c;
            reu(x,y);
            sol[++nr].x=x;
            sol[nr].y=y;
        }
    }
    out<<apm<<"\n";
    out<<nr<<"\n";
    for(i=1;i<=nr;i++)
        out<<sol[i].x<<" "<<sol[i].y<<"\n";

    return 0;
}