/* 
 * File:   main.cpp
 * Author: VirtualDemon
 *
 * Created on April 9, 2010, 8:13 PM
 */
#include <cstdlib>
#include <fstream>
#include <algorithm>
#define Nmax 200010
#define oo 0x3f3f3f3f

/*
 *
 */
using namespace std;
struct vertex
{
    int y, c;
    vertex* next;
} *G[Nmax];
bool uz[Nmax];
int d[Nmax], apm[Nmax];
inline void add( const int& x, const int& y, const int& c )
{
    vertex* q=new vertex, *p=new vertex;
    q->y=y; q->c=c;
    p->y=x; p->c=c;
    q->next=G[x];
    G[x]=q;
    p->next=G[y];
    G[y]=p;
}
int main( void )
{
    vertex* p;
    int N, M, x, y, c, minim, vminim, s;
    ifstream in( "apm.in" );
    in>>N>>M;
    fill( d+1, d+N+1, oo );
    for( ; M; --M )
    {
        in>>x>>y>>c;
        add( x, y, c );
    }
    for( s=0, d[1]=oo-1, x=1; x <= N; ++x )
    {
        for( minim=oo, y=1; y <= N; ++y )
            if( !uz[y] && d[y] < minim )
            {
                minim=d[y];
                vminim=y;
            }
        if( 1 !=vminim )
            s+=minim;
        uz[vminim]=true;
        for( p=G[vminim]; p; p=p->next )
            if( !uz[p->y] && d[p->y] > p->c )
            {
                apm[p->y]=vminim;
                d[p->y]=p->c;
            }
    }
    ofstream out( "apm.out" );
    out<<s<<'\n'<<(N-1)<<'\n';
    for( x=2; x <= N; ++x )
        out<<x<<' '<<apm[x]<<'\n';
    return EXIT_SUCCESS;
}