/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 22, 2010, 1:16 PM
 */
#include <vector>
#include <utility>
#include <fstream>
#include <iterator>
#define inf 0x3f3f3f3f
#define pr pair< int, int >
#define mk pair< int, int >

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