#include <bits/stdc++.h>
#define pi pair<int,int>
using namespace std;

ifstream fin ("apm.in") ;
ofstream fout ("apm.out") ;

const int nmx = 2e5 + 5 ;

int t[nmx] , idk[nmx] ;

int find_root ( int node )
{
    if ( t[node] == node )
        return node ;
    else
        return t[node] = find_root ( t[node] ) ;
}

void unite ( int node_a , int node_b )
{
    int root_a = find_root ( node_a ) ;
    int root_b = find_root ( node_b ) ;

    if ( root_a != root_b )
    {
        if ( idk[root_a] < idk[root_b] )
            t[root_a] = root_b ;
        else if ( idk[root_a] > idk[root_b] )
            t[root_b] = root_a ;
        else
        {
            t[root_a] = root_b ;
            idk[root_b] ++ ;
         }
    }
}

struct apm
{
    int x , y , c ;
};
bool cmp ( apm a , apm b )
{
    return a.c < b.c ;
}

apm a[2*nmx] ;

void solve ()
{

    int n , m ;
    fin >> n >> m ;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        t[i] = i ;
        idk[i] = 1 ;
    }
    for ( int i = 1 ; i <= m ; i ++ )
        fin >> a[i].x >> a[i].y >> a[i].c ;
    sort ( a + 1 , a + m + 1 , cmp ) ;

    long long sum = 0 ;
    vector < pair < int , int > > v ;

    for ( int i = 1 ; i <= m ; i ++ )
    {
        if ( find_root( a[i].x ) != find_root( a[i].y ) )
        {
            sum += a[i].c ;
            v.push_back({ a[i].x , a[i].y }) ;
            unite ( a[i].x , a[i].y ) ;
        }
    }
    fout << sum << '\n' ;
    fout << v.size() << '\n' ;
    for ( auto it : v )
        fout << it.first << " " << it.second << '\n' ;
}

int main()
{
    std :: ios_base :: sync_with_stdio ( false ) ;
    fin.tie(0) ;
    fout.tie(0) ;
    solve() ;

    return 0;
}