// O(MlogM + MlogN)
#include<fstream>
#include<algorithm>
#define inf "apm.in"
#define outf "apm.out"
#define NMax 200100
#define MMax 400100
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int N,M;
int T[NMax],H[NMax];

struct muchie
{
int a;
int b;
int c;
};

muchie m[MMax],arb[NMax];

void read()
{
f>>N>>M;
for(int i=1; i<=M; i++) f>> m[i].a >> m[i].b >> m[i].c ;
}

bool rule(muchie a,muchie b)
{
if( a.c<b.c ) return true;
return false;
}

int Root(int nod)
{
while( T[nod] ) nod = T[nod] ;
return nod;
}

void solve()
{
sort( m+1, m+M+1, rule );
int nrm=1,k=1;
long long cost=0;
while( nrm<=N-1 )
    {
    while( Root( m[k].a ) == Root( m[k].b ) ) k++;
    cost += m[k].c ;
    arb[nrm].a = m[k].a ; arb[nrm].b = m[k].b ;
    nrm++;
    if( H[ m[k].a ] == H[ m[k].b ] )
        {
        T[ m[k].a ] = m[k].b ;
        H[ m[k].b ]++;
        }
    else
        {
        if( H[ m[k].a ] < H[ m[k].b ] ) T[ m[k].a ] = m[k].b;
        else T[ m[k].b ] = m[k].a;
        }
    k++;
    }
g<<cost<<"\n";
g<<nrm-1<<"\n";
for(int i=1; i<nrm; i++) g<< arb[i].a <<" "<< arb[i].b <<"\n";
}

int main()
{
read(); solve();
f.close(); g.close();
return 0;
}