#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int rad [ 250000 ];
int get ( int x )
{
    int aux = x;

    while ( rad [ aux ] > 0 )
    {
        aux = rad [ aux ];
    }


    while ( rad [ x ] > 0 )
    {
        int pux = rad [ x ] ;
        rad [ x ] = aux ;

        x = pux ;
    }

    return aux ;
}

int unite( int a , int b )
{
    int x = get ( a );
    int y = get ( b ) ;


    if ( rad [x  ] < rad [ y ] )
    {
        rad [ x ] += rad[ y ] ;
        rad[ y ] = x ;
    }
    else
    {
        rad [ y ] += rad [ x ] ;
        rad [ x ] = y;
    }
}

bool find ( int x , int y )
{
    if ( get ( x )  == get ( y ) )
        return true ;
    else
        return false;
}


 vector<tuple<int, int, int> > v;

 bool compare( tuple<int ,int , int> x , tuple< int , int , int > y )
 {
     return ( get<2> (x) < get<2> (y)  );
 }
long long n , m ;
int main()
{

    in >> n >> m  ;

    for (int i = 1; i <= n ; i ++ )
        rad [ i ] = -1 ;


        for ( int j = 1 ; j <= m ; j ++ )
        {
            long long  a, b , c;
            in >> a>> b >> c;

            v.push_back(make_tuple(a , b , c ) );
        }

        sort (v.begin() , v.end() , compare  );

        long long sum = 0 ;

        queue<pair<int,int>> q;
        for ( int i = 0 ; i < v.size( ) ; i ++  )
        {
            long long a = get<0> ( v [ i ] );
            long long b = get<1> ( v[ i ] );
            long long c = get<2>  (v [ i ] );
            if ( find ( a , b ) == false )
            {
                unite (a ,b ) ;

                q.push({a,b});
                sum += c;
            }
        }

        out << sum << '\n';

        out << q.size() << '\n';

        while ( !q.empty())
        {
            out << q.front().first << " " << q.front().second << '\n';
            q.pop();
        }



    return 0;
}