#include <stdio.h>
#include <algorithm>
#define mM 400003

using namespace std;

struct m{int x,y,c;} v[mM];

bool cmp(m i,m j)
{
    return(i.c<j.c);
}

int i,N,M,x,y,c,m,a[mM];
bool o[mM];

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=M;i++)
     scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    stable_sort(v+1,v+M+1,cmp);
    for(i=1;i<=M;i++) a[i]=i;
    for(i=1;i<=M;i++)
    {
        x=v[i].x; y=v[i].y;
        while(a[a[x]]!=a[x]) a[x]=a[a[x]];
        while(a[a[y]]!=a[y]) a[y]=a[a[y]];
        if(a[x]!=a[y])
        {
            a[x]=a[y]=a[max(a[x],a[y])]=min(a[x],a[y]);
            o[i]=1; c+=v[i].c; m++;
        }
    }
    printf("%d\n%d\n",c,m);
    for(i=1;i<=M;i++) if(o[i])
     printf("%d %d\n",v[i].x,v[i].y);
    return 0;
}