#include<cstdio>
#include<fstream>
#include<algorithm>
using namespace std;
FILE *f=fopen("apm.in","r");
ofstream g("apm.out");
int tata[200002],dim[200002];
struct elem
{
    int x,y,c;
};
elem v[400002];

inline bool cmp(const elem &a,const elem &b)
{
    return a.c<b.c;
}

struct muchie
{
    int x,y;
};
muchie w[200002];

int tata_multime(int x)
{
    if(x!=tata[x])
        tata[x] = tata_multime(tata[x]);
    return tata[x];
}

void unire(int x,int y)
{
    x=tata_multime(x);
    y=tata_multime(y);
    if(dim[x]<dim[y])
    {
        dim[y]+=dim[x];
        tata[x]=y;
    }
    else
    {
        dim[x]+=dim[y];
        tata[y]=x;
    }
}

int main()
{
    int n,m,sol=0,k=0,i;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
        fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;i++)
        tata[i]=i,dim[i]=1;
    i=1;
    while(k<=n-2)
    {
        if(tata_multime(v[i].x)!=tata_multime(v[i].y))
        {
            unire(v[i].x,v[i].y);
            k++;
            w[k].x=v[i].x;
            w[k].y=v[i].y;
            sol+=v[i].c;
        }
        i++;
    }
    g<<sol<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        g<<w[i].x<<" "<<w[i].y<<'\n';
    return 0;
}