#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;
            if(tx<ty)
                t[a[i].y]=tx;
            else t[a[i].x]=ty;
        }
        else if(tx==-1&&ty>-1)
        {
            v[++v[0]]=i;
            cost+=a[i].c;
            t[a[i].x]=ty;
        }
        else if(ty==-1&&tx>-1)
        {
            v[++v[0]]=i;
            cost+=a[i].c;
            t[a[i].y]=tx;
        }
    }
        /*if(comp[a[i].x].comp!=comp[a[i].y].comp)
        {

            v[++v[0]]=i;
            cost+=a[i].c;
            int t,k,x;
            if(comp[a[i].x].comp<comp[a[i].y].comp)
                k=a[i].x,t=a[i].y;
            else k=a[i].y,t=a[i].x;
            while(comp[k].comp!=comp[t].t)
            {
                comp[t].comp=comp[k].comp;
                x=comp[t].t;
                comp[t].t=comp[k].t;
                t=x;
            }


            int k=comp[a[i].y],t=comp[a[i].x];
            for(int j=1;j<=n;j++)
                if(comp[j]==k||comp[j]==t)
                comp[j]=min(k,t);



        }*/
    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;
}