#include <algorithm>
#include <cstdio>

using namespace std;

const int MAX=200014;
struct multime {
    int a , b , cost ;
    void scan ( )
    {
        scanf ("%d %d %d " , &a , &b , &cost ) ;
    }
};multime q [ MAX ] ;

int tata [ MAX ] , nod [  MAX ] ;

struct muchiile {
    int c,d;
    void sett ( int a , int b )
    {
        c = a ;
        d = b ;
    }
};muchiile sol[MAX];

bool cmp ( multime a , multime b )
{
    return a.cost < b.cost ;
    // sort ( q +1 , q + m + 1 , cmp ) ;
}

int findtata (int x)
{
    int r=x;
    // gasire tata
    while(r!=tata[r])
    r=tata[r];
    // unire a fiecarei componenente a multimii cu multimea tata
    while (tata[x]!=x)
    {
        int aux=tata[x];
        tata[x]=r;
        x=aux;
    }
    return r ;
}
void unire(int a ,int b)
{
    a=findtata(a);
    b=findtata(b);
    if (nod[a]>nod[b])
    {
        nod[a]=nod[a]+nod[b];
        tata[b]=a;
    }
    else
    {
        nod[b]=nod[b]+nod[a];
        tata[a]=b;
    }
}
int main(       )
{
    freopen ("apm.in" , "r" , stdin );
    freopen ("apm.out" , "w" , stdout );
    int n,m,cost=0,nr=0;
    scanf ("%d %d" , &n ,&m);
    for ( int i = 1 ; i <= n ; ++i )
        {
            tata[i]=i;
            nod[i]=1;
        }
    for ( int i = 1 ; i <= m ; ++i )
        q[i].scan();
    sort (q+1,q+m+1,cmp);
    for ( int i = 1 ; i <= m ; ++i )
       if (findtata(q[i].a)!=findtata(q[i].b))
                {
                  unire(q[i].a,q[i].b);
                  cost=cost+q[i].cost;
                  nr++;
                  sol[nr].sett ( q [ i ].a , q [ i ].b ) ;
                }
    printf ("%d\n%d\n" , cost , nr );

    for ( int i = 1 ; i <= nr ; ++i )
        printf("%d %d\n" , sol[i].c , sol[i].d );
    return 0;
}