#include <fstream>
#include <vector>
#define infinity 0x3f3f3f3f

using namespace std ;

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

int n ;
vector < pair <int,int> > G[200002] ;
int d[20002] , t[200002] , v[200002] ;
int c_min ;

void citire ()
{
    int m ;
    f >> n >> m ;
    for ( ; m ; --m )
    {
         int i , j , c ;
         f >> i >> j >> c ;
         G[i].push_back ( make_pair ( j , c ) ) ;
         G[j].push_back ( make_pair ( i , c ) ) ;
    }
}
void afisare ()
{
    g << c_min << "\n" << n - 1 << "\n" ;
    for ( int i = 1 ; i <= n ; ++i )
        if ( t[i] )
            g << i << " " << t[i] << "\n" ;
}
void prim ( int start )
{
    //pregatim vectorii
    for ( int i = 1 ; i <= n ; ++i )
        v[i] = 0 , t[i] = -1 , d[i] = infinity ;
    v[start] = 1 , t[start] = 0 , d[start] = 0 ;
    for ( vector < pair <int,int> > :: iterator I = G[start].begin() ; I < G[start].end() ; ++I )
        t[ I -> first ] = start , d[ I -> first ] = I -> second ; // sau t[(*I).first] = start , d[(*I).first] = (*I).second ;
    d[0] = infinity ;
    for ( int cnt = 1 ; cnt < n ; ++cnt )
    {
        int nod = 0 ;
        for ( int i = 1 ; i <= n ; ++i )
            if ( v[i] == 0 )
                if ( d[i] < d[nod] )
                    nod = i ;
        /* daca ar fi neconex
        if ( nod == 0 )
            break ;
        */
        v[nod] = 1 ;
        c_min += d[nod] ;
        for ( vector < pair <int,int> > :: iterator I = G[nod].begin() ; I < G[nod].end() ; ++I )
            if ( v[ I -> first] == 0 && d[ I -> first] > I -> second )
                d[I -> first] = I -> second , t[I -> first] = nod ;
    }
}

int main ()
{
    citire () ;
    prim (1) ;
    afisare () ;
    return 0 ;
}