#include <cstdio>
#include<algorithm>
using namespace std;
int tx,ty,cost,n,m,i,v[400003];
struct rec{int x,y,c;}a[400003];
int t[200003];
int cmp(rec a,rec b)
{
    if(a.c>b.c)return 0;
    else return 1;
}
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",&a[i].x,&a[i].y,&a[i].c);
    sort(a+1,a+1+m,cmp);
    for(i=1;i<=n;i++)
        t[i]=-1;
    for(i=1;i<=m&&v[0]<n-1;i++)
    {
        tx=t[a[i].x];
        ty=t[a[i].y];
        while(tx>-1&&t[tx]!=-1)
          tx=t[tx];
        while(ty>-1&&t[ty]!=-1)
          ty=t[ty];
        if(tx==-1&&ty==-1)
        {
            v[++v[0]]=i;
            cost+=a[i].c;
            if(a[i].x<a[i].y)
                t[a[i].y]=a[i].x;
            else t[a[i].x]=a[i].y;
        }
        else if(tx>-1&&ty>-1&&tx!=ty)
        {
            v[++v[0]]=i;
            cost+=a[i].c;
            t[tx]=a[i].y;
        }
        else if(tx==-1&&ty>-1)
        {
            v[++v[0]]=i;
            cost+=a[i].c;
            t[a[i].x]=a[i].y;
        }
        else if(ty==-1&&tx>-1)
        {
            v[++v[0]]=i;
            cost+=a[i].c;
            t[a[i].y]=tx;
        }
    }
    printf("%d\n%d\n",cost,v[0]);
    for(i=1;i<=v[0];i++)
        printf("%d %d\n",a[v[i]].x,a[v[i]].y);
    return 0;
}