#include<cstdio>
#include<algorithm>
using namespace std;
struct much {int a,b,c;};
much /*op much*/ v[400001];
int rad[200001];
bool sortare( much a, much b)
    {if(a.c<b.c||(a.c==b.c&&a.a<b.a)||(a.c==b.c&&a.a==b.a&&a.b<b.b))
        return 1;
    return 0;
    }
int radacina( int nod )
    {if(rad[nod]==nod)
        return nod;
    else
        {rad[nod]=radacina(rad[nod]);
        return rad[nod];
        }
    }
int vec[400001];
int main ()
{freopen ("apm.in","r",stdin);
freopen ("apm.out","w",stdout);
int n,m,i,s=0,x=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
    scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].c);
sort(v+1,v+m+1,sortare);
for(i=1;i<=n;i++)
    rad[i]=i;
for(i=1;i<=m;i++)
    {rad[v[i].a]=radacina(v[i].a);
    rad[v[i].b]=radacina(v[i].b);
    if(rad[v[i].a]<rad[v[i].b])
        {s+=v[i].c;
        rad[v[i].b]=rad[v[i].a];
        x++;
        vec[x]=i;
        }
    if(rad[v[i].a]>rad[v[i].b])
        {s+=v[i].c;
        rad[v[i].a]=rad[v[i].b];
        x++;
        vec[x]=i;
        }
    }
printf("%d\n%d\n",s,x);
for(i=1;i<=x;i++)
    printf("%d %d\n",v[vec[i]].a,v[vec[i]].b);
return 0;
}