#include <bits/stdc++.h>
#define mp make_pair
using namespace std ;
const int NR = 200002 ;
const int NRM = 400001 ;
ifstream in ("apm.in") ;
ofstream out ("apm.out") ;
int father [ NR ] , grupa [ NR ] ;
deque < pair < int , int > > st ;
struct edge
{
    int x , y , cost ;
}e [ NRM ];
int find_root ( int x )
{
    int root , y ;
    for( root = x ; root != father [ root ]  ; root = father [ root ] ) ;

    for ( ; x != father[ x ] ;  )
    {
        y = father [ x ] ;
        father [ x ] = root ;
        x = y ;
    }
    return root ;
}
void unite ( int x , int y )
{
    if ( grupa [ x ] > grupa [ y ] )    father [ y ] = x ;
    else                                father [ x ] = y ;
    if ( grupa [ x ] == grupa [ y ] )   grupa [ y ] ++ ;
}
bool cmp ( edge i , edge j )
{
    return i.cost < j.cost ;
}
int main ()
{
    int  i , n , m , root1 , root2 , cash = 0 , nr = 0 ; in >> n >> m ;
    for ( i = 1 ; i <= m ; ++ i )
    {
        in >> e [ i ].x >> e [ i ].y >> e [ i ].cost ;
    }
    sort ( e + 1 , e + m + 1 , cmp ) ;
    for ( i = 1 ; i <= n ; ++ i )   father [ i ]= i , grupa [ i ] = 1 ;
    for ( i = 1 ; nr < n - 1 ; ++ i )
    {
        root1 = find_root( e [ i ].x ) ;
        root2 = find_root( e [ i ].y ) ;
        if ( root1 != root2 )
        {
            unite( root1 , root2 ) ;
            nr ++ ;
            cash += e [ i ].cost ;
            st.push_back( mp ( e [ i ].y , e [ i ].x ) ) ;
        }
    }
    out << cash << "\n" << n - 1 << "\n" ;
    for ( size_t j = 0 ; j < st.size() ; ++ j ) out << st [ j ].first << " " << st[ j ].second << "\n";
}