#include <bits/stdc++.h>
#define N 200005

using namespace std;

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

struct muchie
{
    int cst, x , y ;
};
muchie mc[2*N] ;

int n , m , r[N] , par[N] ;
vector<int> muc ;
int sol;

bool cmp(muchie m1,muchie m2)
{
    return m1.cst < m2.cst ;
}


void citire()
{
    int i , a , b , c ;
    fin >> n >> m ;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> a >> b >> c ;
        mc[i] = {c,b,a} ;
    }
    sort(mc+1,mc+1+m,cmp) ;
}

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

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

void solve()
{
    int i , r1 , r2 ;
    for ( i = 1 ; i <= n ; i++ )
        par[i] = i ;
    for ( i = 1 ; i <= m ; i++ )
    {
        r1 = root(mc[i].x) ;
        r2 = root(mc[i].y) ;
        if ( r1 != r2 )
        {
            unite(r1,r2) ;
            sol = sol + mc[i].cst ;
            muc.push_back(i) ;
        }
    }
}

int main()
{
    citire() ;
    solve() ;
    fout << sol << '\n' ;
    fout << muc.size() << '\n' ;
    for ( int i = 0 ; i < muc.size() ; i++ )
        fout << mc[muc[i]].x << " " << mc[muc[i]].y << '\n' ;
}