/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on May 9, 2010, 2:34 PM
 */
#include <vector>
#include <cstdlib>
#include <fstream>
#define Nmax 200011
#define oo 0x3f3f3f3f

/*
 * 
 */
using namespace std;
typedef pair< int, int > pr;
bool was[Nmax];
int apm[Nmax], d[Nmax];
vector< pr > G[Nmax];
vector< pr >::iterator it, iend;
int main(int argc, char** argv)
{
    int N, M, x, y, c, s, min;
    ifstream in( "apm.in" );
    for( in>>N>>M; M; --M )
    {
        in>>x>>y>>c;
        G[x].push_back( pr( y, c ) );
        G[y].push_back( pr( x, c ) );
    }
    fill( d, d+N+1, oo );
    s=d[1]=0;
    while( true )
    {
        min=0;
        for( y=1; y <= N; ++y )
            if( !was[y] && d[y] < d[min] )
                min=y;
        if( !min )
            break;
        s+=d[min];
        was[min]=true;
        for( it=G[min].begin(), iend=G[min].end(); it < iend; ++it )
        {
            y=it->first; c=it->second;
            if( !was[y] && d[y] > c )
            {
                d[y]=c;
                apm[y]=min;
            }
        }
    }
    ofstream out( "apm.out" );
    out<<s<<' '<<(N-1)<<'\n';
    for( x=2; x <= N; ++x )
        out<<x<<' '<<apm[x]<<'\n';
    return (EXIT_SUCCESS);
}