#include <iostream>
#include <fstream>
#include <vector>

using namespace std ;

ifstream f("apm.in");
ofstream g("apm.out") ;

const int Nmax = 200001;
const int Infinity = 1e9;
int V[Nmax], T[Nmax], D[Nmax], n, m, cost_minim ;
vector < pair <int,int> > G[Nmax] ;
vector < pair <int,int> > Ans ;
int Heap[2*Nmax+10] , lg_heap ;
int Position_in_heap[Nmax] ;

void promovare ( int k )
{
    bool este_heap = false;
    while ( !este_heap )
    {
        if ( k == 1 )
            este_heap = true ;
        else
        {
            if ( D[Heap[k]] < D[Heap[k/2]] )
            {
                swap ( Heap[k] , Heap[k/2] ) ;
                Position_in_heap[Heap[k]] = k ;
                Position_in_heap[Heap[k/2]] = k / 2;
                k /= 2;
            }
            else
                este_heap = true ;
        }
    }
}

void cernere ( int k )
{
    bool este_heap = false;
    while ( !este_heap )
    {
        if ( Heap[2*k] == 0 )
            este_heap = true ;
        else
        {
            int fiu = 2*k ;
            if ( D[Heap[fiu+1]] < D[Heap[fiu]] )
                ++fiu ;
            if ( D[Heap[k]] > D[Heap[fiu]] )
            {
                swap ( Heap[k] , Heap[fiu] ) ;
                Position_in_heap[Heap[k]] = k ;
                Position_in_heap[Heap[fiu]] = fiu;
                k = fiu;
            }
            else
                este_heap = true ;
        }
    }
}


int main ()
{
    f >> n >> m ;
    for ( int cnt = 1 ; cnt <= m ; ++cnt)
    {
        int i, j, c;
        f >> i >> j >> c;
        G[i].push_back ( make_pair ( j , c ) ) ;
        G[j].push_back ( make_pair ( i , c ) ) ;
    }
    for ( int i = 0 ; i <= n ; ++i)
        D[i] = Infinity;
    V[1] = 1;
    for ( const pair <int,int> & x : G[1] )
    {
        T[x.first] = 1;
        D[x.first] = x.second;
        Heap[++lg_heap] = x.first;
        Position_in_heap[x.first] = lg_heap;
        promovare ( lg_heap );
    }
    for ( int steps = 1 ; steps < n ; ++steps )
    {
        int nod = Heap[1] ;
        V[nod] = 1 ;
        cost_minim += D[nod];
        swap ( Heap[1] , Heap[lg_heap] ) ;
        Position_in_heap[Heap[1]] = 1 ;
        Position_in_heap[Heap[lg_heap]] = lg_heap;
        Heap[lg_heap] = 0;
        --lg_heap ;
        cernere ( 1 ) ;
        Position_in_heap[nod] = 0;
        for ( const pair <int,int> & x : G[nod] )
            if ( V[x.first] == 0 && D[x.first] > x.second )
            {
                D[x.first] = x.second;
                T[x.first] = nod;
                if ( Position_in_heap[x.first] == 0 )
                {
                    Heap[++lg_heap] = x.first;
                    Position_in_heap[x.first] = lg_heap;
                    promovare ( lg_heap );
                }
                else
                {
                    promovare ( Position_in_heap[x.first] );
                }
            }
    }
    for ( int i = 1 ; i <= n ; ++i )
        if ( T[i] )
            Ans.push_back ( make_pair ( i , T[i] ) );
    g << cost_minim << "\n";
    g << n - 1 << "\n" ;
    for ( const pair<int,int> & x : Ans )
        g << x.first << " " << x.second << "\n";
    return 0;
}