///FLAVIUS, UBESTE-MA
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


ifstream fin( "apm.in" );
ofstream fout("apm.out");
int DSU[ 200010 ],i,j,n,m,x,y,ans,k;

pair< int , pair< int , int > > v[400010];

int Union( int x )
{
    if( x == DSU[ x ] )
        return x;
    int a = Union( DSU[ x ] );
    DSU[ x ] = a;
    return a;
}

int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>v[ i ].second.first>>v[ i ].second.second>>v[ i ].first;
    }
    sort( v + 1 , v + m + 1 );
    for( i = 1 ; i <= n ; i++ )
    {
        DSU[ i ] = i;
    }

    for( i = 1 ; i <= m ; i++ )
    {
        if( Union( v[ i ].second.first ) != Union( v[ i ].second.second ) )
        {
            DSU[ Union( v[ i ].second.first ) ] = Union( v[ i ].second.second );
            ans += v[ i ].first;
            ++k;
        }
        if( k == n - 1 )
        {
            fout<<ans<<'\n'<<n-1<<'\n';
            break;
        }
    }
    for( i = 1 ; i <= n ; i++ )
    {
        DSU[ i ] = i;
    }
    for( i = 1 ; i <= m ; i++ )
    {
        if( Union( v[ i ].second.first ) != Union( v[ i ].second.second ) )
        {
            DSU[ Union( v[ i ].second.first ) ] = Union( v[ i ].second.second );
            ++k;
            fout<<v[ i ].second.first<<' '<<v[ i ].second.second<<'\n';
        }
        if( k == n - 1 )
        {
            break;
        }
    }

    return 0;
}