#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

const int NMAX = 1e5 ;

struct muchie
{
    int x , y , cost , sel ;
} ;

muchie v [ NMAX + 5 ] ;
int h [ NMAX + 5 ] , t [ NMAX + 5 ] ;

bool cmp ( const muchie & a , const muchie & b )
{
    return a.cost < b.cost ;
}

int FindSet ( int poz )
{
    while ( t [ poz ] != poz )
        poz = t [ poz ] ;

    return poz ;
}

int UnionSet ( int x , int y )
{
    if ( h [ x ] == h [ y ] )
    {
        t [ y ] = x ;
        ++ h [ x ] ;
    }
    else
        if ( h [ x ] > h [ y ] )
            t [ y ] = x ;
        else
            t [ x ] = y ;
}

int main()
{
    ifstream cin ( "apm.in" ) ;
    ofstream cout ( "apm.out" ) ;

    int n , m , i , a , b , c , nr = 0 , cnt = 0 ;
    long long ans = 0 ;

    cin >> n >> m ;

    for ( i = 1 ; i <= n ; ++ i )
        h [ i ] = 1 , t [ i ] = i ;

    for ( i = 1 ; i <= m ; ++ i )
    {
        cin >> a >> b >> c ;
        v [ i ].x = a ;
        v [ i ].y = b ;
        v [ i ].cost = c ;
    }

    sort ( v + 1 , v + m + 1 , cmp ) ;

    for ( i = 1 ; i <= m && nr < n ; ++ i )
    {
        a = FindSet ( v [ i ].x ) ;
        b = FindSet ( v [ i ].y ) ;

        if ( a != b )
        {
            ++ nr ;
            UnionSet ( a , b ) ;
            v [ i ].sel = 1 ;
            ++ cnt ;
            ans += v [ i ].cost ;
        }
    }

    cout << ans << '\n' << cnt << '\n' ;

    for ( i = 1 ; i <= m ; ++ i )
        if ( v [ i ].sel )
            cout << v [ i ].x << ' ' << v [ i ].y << '\n' ;

    return 0;
}