#include <bits/stdc++.h>
#define NMAX 200001

using namespace std;

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

bool compar(pair<pair<int,int>,int> p1 , pair<pair<int,int>,int> p2  )
{
    return p1.second < p2.second ;
}

vector<pair<pair<int,int>,int> > edge ;
int n , m ;
int parinte[NMAX] , sol[NMAX] , r[NMAX] , k = 0 , suma = 0 ;

void citire()
{
    int i , x , y , z;
    fin >> n >> m ;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> z ;
        edge.push_back(make_pair(make_pair(x,y),z)) ;
    }
    sort(edge.begin(),edge.end(),compar) ;
    memset(r,0,4*n+4);
}

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

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

void solve()
{
    int i , r1 , r2 ;
    for ( i = 1 ; i <= n ; i++ )
        parinte[i] = i ;
    for ( i = 0 ; i < m ; i++ )
    {
        r1 = root(edge[i].first.first) ;
        r2 = root(edge[i].first.second) ;
        if ( r1 != r2 )
        {
            unite(r1,r2) ;
            sol[++k] = i ;
            suma = suma + edge[i].second ;
        }
    }
}

int main()
{
    citire() ;
    solve() ;
    fout << suma << '\n' ;
    fout << k << '\n' ;
    for ( int i = 1 ; i <= k ; i++ )
        fout << edge[sol[i]].first.first << " " << edge[sol[i]].first.second << '\n' ;
}