#include<stdio.h>
#define nmax 200005
#define mmax 400005
long v[nmax],n,m,cs,w;
 
struct muchii
{
    long i,j,c;
};
 
muchii x[mmax],sol[nmax];
 
struct nod
{
    long info;
    nod *urm;
};
 
nod *t[nmax];
 
void read()
{
    scanf("%ld%ld",&n,&m);
    long i;
    for (i=1;i<=m;i++)
    {
        scanf("%ld%ld%ld",&x[i].i,&x[i].j,&x[i].c);
    }
}
 
long part(long st,long dr)
{
    long p,i,j;
    muchii aux;
    i=st-1;
    j=dr+1;
    p=x[(st+dr)/2].c;
    while (1)
    {
        do {i++;} while (x[i].c<p);
        do {j--;} while (x[j].c>p);
        if (i<j)
        {
            aux=x[i];
            x[i]=x[j];
            x[j]=aux;
        }
        else return j;
    }
     
}
 
void quicks(long st,long dr)
{
    long p;
    if (st<dr)
    {
        p=part(st,dr);
        quicks(st,p);
        quicks(p+1,dr);
    }
}
 
void init()
{
    long i;
    nod *p;
    for (i=1;i<=n;i++)
    {
        v[i]=i;
        p=new nod;
        p->info=i;
        p->urm=t[i];
        t[i]=p;
    }
}
 
void connect(long a,long b)
{
    nod *aux,*p;
    long r,s;
    r=v[a];
    s=v[b];
    p=t[s];
    while (p)
    {
        aux=p;
        t[s]=p->urm;
        p=t[s];
        v[aux->info]=r;
        aux->urm=t[r];
        t[r]=aux;
    }
}
     
void rez()
{
    long k=n-1,i;
    for (i=1;i<=m;i++)
    {
        if (v[x[i].i]!=v[x[i].j])
        {
            cs+=x[i].c;
            if (v[x[i].i]<v[x[i].j])
                connect(x[i].i,x[i].j);
            else connect(x[i].j,x[i].i);
            sol[++w]=x[i];
            k--;
        }
    }
}
 
void print()
{
    printf("%ld\n",cs);
    printf("%ld\n",w);
    long i;
    for (i=1;i<=w;i++)
    {
        printf("%ld %ld\n",sol[i].i,sol[i].j);
    }
}
 
 
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    init();
    quicks(1,m);
    rez();
    print();
    return 0;
}