#include<stdio.h>
#include<algorithm>
using namespace std;
struct sp
{
    unsigned x,y;
    int c;
}v[400005];
unsigned t[200005],p[200005],s[200005];
bool cm(sp a,sp b)
{
    return a.c<b.c;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
unsigned n,m,i,x,y,l;
int c=0;
scanf("%u%u",&n,&m);
for(i=1;i<=m;i++)
{
    scanf("%u%u%d",&v[i].x,&v[i].y,&v[i].c);
}
sort(v+1,v+m+1,cm);
l=0;
for(i=1;i<=m;i++)
{
    x=v[i].x;
    y=v[i].y;
    while(t[x]!=0)
        x=t[x];
    while(t[y]!=0)
        y=t[y];
        if(x!=y)
        {
            l++;
            s[l]=i;
            c=c+v[i].c;
        if(p[x]>p[y])
        {
            t[y]=x;
        }
        else
            if(p[y]>p[x])
        {
            t[x]=y;
        }
        else
        {
            t[y]=x;
            p[x]++;
        }
        }
}
printf("%d\n%u\n",c,l);
for(i=1;i<=l;i++)
    printf("%u %u\n",v[s[i]].x,v[s[i]].y);
    return 0;
}