#include <stdio.h>
 
#define Nmax 128
 
int a[4][Nmax],n,m,c,t[Nmax],nr,rang[Nmax];
 
int mult(int x)
{
    if(x!=t[x])
        t[x]=mult(t[x]);
    return t[x];
}
 
void combina(int x,int y)
{
    x=mult(x);
    y=mult(y);
    if(rang[x]>rang[y]) t[y]=x; else
    if(rang[y]>rang[x]) t[x]=y; else
    {
        t[x]=y;
        ++rang[y];
    }
}
 
 
void swap(int i,int j)
{
        int tmp;
        tmp=a[2][i];
        a[2][i]=a[2][j];
        a[2][j]=tmp;
        tmp=a[1][i];
        a[1][i]=a[1][j];
        a[1][j]=tmp;
        tmp=a[0][i];
        a[0][i]=a[0][j];
        a[0][j]=tmp;
}
 
 
void qsort(int st,int dr)
{
    int i=st,j=dr,x=a[2][(i+j)/2];
    do
    {
            while(a[2][i]<x) ++i;
            while(a[2][j]>x) --j;
            if(i<=j)
                {
                    swap(i,j);
                    ++i;
                    --j;
                }
    }while(i<=j);
 
    if(st<j) qsort(st,j);
    if(i<dr) qsort(i,dr);
}
 
 
int main()
{
    int i;
    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[0][i],&a[1][i],&a[2][i]);
    qsort(1,m);
    for(i=1;i<=n;++i)
        {
            t[i]=i;
        }
    for(i=1;i<=m;++i)
        {
            if(mult(a[0][i])!=mult(a[1][i]))
                {
                    combina(a[0][i],a[1][i]);
                    c+=a[2][i];
                    a[3][i]=1;
                    ++nr;
                }
        }
    printf("%d\n",c);
    printf("%d\n",nr);
    for(i=1;i<=m;++i)
        {
            if(a[3][i]==1)
                printf("%d %d\n",a[0][i],a[1][i]);
        }
    return 0;
}