#include <stdio.h>
#include<algorithm>
using namespace std;
struct pct
{
    long x,y,z;
}a[400002],c[200001];
long b[200001],d[200001],c1,c2;
int cmp(pct x, pct y)
{
    if (x.z>y.z)
        return 0;
    else
        return 1;
}
long n,m,i,j,sum,u;
long sch (long x)
{
    long y;
    y=x;
    while (d[y]!=y)
    {
        y=d[y];
    }
    while (d[x]!=x)
    {
        x=d[x];
        d[x]=y;
    }
    return y;
}
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf ("%ld%ld",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf ("%ld%ld%ld",&a[i].x,&a[i].y,&a[i].z);
    }
    for (i=1;i<=n;i++)
        b[i]=0;
    sort (&a[1],&a[m+1],cmp);
    j=1;
    i=1;
    sum=0;
    u=0;
    while (j<n)
    {
        c1=b[a[i].x];
        c2=b[a[i].y];
        if (c1==0&&c2==0)
        {
            c[j]=a[i];
            j++;
            u++;
            b[a[i].x]=u;
            b[a[i].y]=u;
            d[u]=u;
            sum+=a[i].z;
        }
        else
            if (c1==0&&c2!=0)
            {
                c[j]=a[i];
                j++;
                b[a[i].x]=sch(b[a[i].y]);
                sum+=a[i].z;
            }
            else
                if (c1!=0&&c2==0)
                {
                c[j]=a[i];
                j++;
                b[a[i].y]=sch(b[a[i].x]);
                sum+=a[i].z;
                }
                else
                if (sch(c1)!=sch(c2))
                {
                    d[c2]=d[c1];
                    c[j]=a[i];
                    j++;
                    b[a[i].y]=sch(c1);
                    sum+=a[i].z;
                }
        i++;
    }
    printf ("%ld\n%ld\n",sum,j);
    for (i=1;i<j;i++)
        printf ("%ld %ld\n",c[i].x,c[i].y);
    return 0;
}