#include <bits/stdc++.h>

using namespace std;

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

struct muchie
{
    int x , y , c;
};
muchie edge[400001] ;
int r[200001] , parinte[200001] ;
int n , m, k =1 , sol= 0 ;
int solm[400001] ;

bool compar ( muchie m1 , muchie m2 )
{
    return m1.c < m2.c ;
}

void citire()
{
    int i ;
    fin >> n >> m ;
    for ( i = 1 ; i <= m ; i++ )
        fin >> edge[i].x >> edge[i].y >> edge[i].c ;
    sort(edge+1,edge+m+1,compar) ;
}

int root ( int x)
{
    while(x != parinte[x] )
        x = parinte[x] ;
    return x;
}

void unite ( int a , int b)
{
    if ( r[a] < r[b] )
        parinte[a] = parinte[b] ;
    else if ( r[a] > r[b] )
        parinte[b] = parinte[a] ;
    else if ( r[a] == r[b] )
    {
        parinte[a] = parinte[b] ;
        r[b]++ ;
    }
}

void solve()
{
    int i ;
    for ( i = 1 ; i <= n ; i++ )
        parinte[i] = i ;
    for ( i = 1 ; i <= m ; i++ )
    {
        int r1 = root(edge[i].x) ;
        int r2 = root(edge[i].y) ;
        if ( r1 != r2 )
        {
            unite(r1,r2) ;
            sol = sol + edge[i].c ;
            solm[k] = i;
            k++ ;
        }
    }
}

int main()
{
    citire() ;
    solve() ;
    fout << sol << '\n' ;
    fout << k-1 << '\n' ;
    for ( int i = 1 ; i < k ; i++ )
        fout << edge[solm[i]].x << " " << edge[solm[i]].y << '\n' ;
}