#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,a,b;
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=a=v[i].x;
    y=b=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])
        {
            while(t[a]!=0)
            {
                b=a;
                p[a]=0;
                a=t[a];
                t[b]=y;
            }
            t[a]=y;
        }
        else
        {
           while(t[b]!=0)
           {
               a=b;
               p[b]=0;
               b=t[b];
               t[a]=x;
           }
           t[b]=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;
}