/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on December 22, 2009, 1:06 PM
 */
#include <vector>
#include <utility>
#include <fstream>
#include <iterator>
#define inf 1<<30
#define pb push_back
#define mk make_pair< int, int >

/*
 *
 */
using namespace std;
vector<bool> uz;
vector<int> cmin, apm;
vector< vector< pair< int, int > > > v;
vector< pair< int, int > >::const_iterator it, iend;
int main()
{int n, m, i, x, y, c, s=0, minim, nod;
    ifstream in("apm.in");
    in>>n>>m;
    v.resize(n);
    cmin.resize(n);
    cmin.assign(n, inf );
    for( i=0; i < m; ++i )
    {
        in>>x>>y>>c;
        v[x-1].pb( mk( y-1, c ) );
        v[y-1].pb( mk( x-1, c ) );
        if( 1 == x )
            cmin[y-1]=c;
        if( 1 == y )
            cmin[x-1]=c;
    }
    uz.resize(n);
    apm.resize(n);
    uz[0]=true;
    for( m=1; m < n; ++m )
    {minim=inf;
        for( i=0; i < n; ++i ) //get the minim vertex
            if( !uz[i] && minim > cmin[i] )
                minim=cmin[i], nod=i;
        s+=minim;
        uz[nod]=true;
        //update the array 
        for( it=v[nod].begin(), iend=v[nod].end(); it != iend; ++it )
            if( !uz[it->first] && it->second < cmin[it->first] )
                apm[it->first]=nod, cmin[it->first]=it->second;
    }
    ofstream out("apm.out");
    out<<s<<'\n'<<(n-1)<<'\n';
    for( i=1; i < n; ++i )
       out<<(i+1)<<' '<<(apm[i]+1)<<'\n';
    return 0;
}