// 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;
}

inline void Reuneste(int v1,int v2)
{
if( H[ v1 ] == H[ v2 ] )
    {
    T[ v2 ] = v1 ;
    H[ v1 ]++;
    return;
    }
if( H[ v2 ] < H[ v1 ] ) { T[ v2 ] = v1; return; }
T[ v1 ] = v2;
}

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

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