#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 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)
        V[i] = 0, T[i] = -1, D[i] = Infinity;
    V[1] = 1;
    T[1] = 0;
    for ( const pair<int,int> & x : G[1] )
    {
        T[x.first] = 1;
        D[x.first] = x.second;
    }
    for ( int steps = 1 ; steps < n ; ++steps )
    {
       int nod = 0;
       for ( int j = 1 ; j <= n ; ++j)
          if ( V[j] == 0 && D[j] < D[nod] )
            nod = j;
       if ( nod == 0 )  break;
       V[nod] = 1;
       cost_minim += D[nod];
       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 ;
    }
    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;
}