#include <cstdio>
using namespace std;

int n,m,d=0,a[400000][3],grupa[200001],muchii[400000][2];

void read()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i)
    {
        scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
    }
}

void quick(int s,int d)
{
    int m=a[(s+d)/2][2],i=s,j=d,aux;
    while(i<=j)
    {
        while(a[i][2]<m) ++i;
        while(a[j][2]>m) --j;
        if(i<=j)
        {
            aux=a[i][0];
            a[i][0]=a[j][0];
            a[j][0]=aux;
            aux=a[i][1];
            a[i][1]=a[j][1];
            a[j][1]=aux;
            aux=a[i][2];
            a[i][2]=a[j][2];
            a[j][2]=aux;
            ++i;--j;
        }
    }
    if(i<d) quick(i,d);
    if(j>s) quick(s,j);
}

int gr(int x)
{
    if(grupa[x]==x) return x;
    grupa[x]=gr(grupa[x]);
    return grupa[x];
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    quick(0,m-1);
    int i,x,y;
    for(i=1;i<=n;++i) grupa[i]=i;
    m=0;
    --n;
    i=0;
    while(m<n)
    {
        x=gr(a[i][0]);
        y=gr(a[i][1]);
        if(x!=y)
        {
            d+=a[i][2];
            grupa[y]=x;
            muchii[m][0]=a[i][0];
            muchii[m++][1]=a[i][1];
        }
        ++i;
    }
    printf("%d\n%d\n",d,m);
    for(i=0;i<m;++i)
    {
        printf("%d %d\n",muchii[i][0],muchii[i][1]);
    }
    return 0;
}