#include <bits/stdc++.h>
#define N 200008

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
struct muchii
{
    int x, y;
    int c;
} v[N];

int Dad[N], Rang[N];

inline bool cmp( muchii x, muchii y )
{
    return x.c < y.c;
}

void Citire()
{
    int i;
    fin >> n >> m;
    for( i=1; i<=m; i++ )
    {
        fin >> v[i].x >> v[i].y >> v[i].c;
    }
    sort( v + 1, v + m + 1, cmp );

    for( i=1; i<=n; i++ )
        Dad[i] = i, Rang[i] = 1;
}

int Find( int x )
{
    return ( Dad[x] == x ) ? x : Find( Dad[x] );
}

void Union( int x, int y )
{
    int xx = Find(x);
    int yy = Find(y);
    if( Rang[xx] > Rang[yy] )
        swap( xx, yy );
    Dad[xx] = yy;
    Rang[yy] += Rang[xx];
}

int k;
muchii sol[N];

void Rezolvare()
{
    int i;
    int x, y;
    int s = 0;
    for( i=1; i<=m; i++ )
    {
        x = v[i].x;
        y = v[i].y;
        if( Find(x) != Find(y) )
            Union( x, y ), s += v[i].c, sol[++k] = v[i];
    }

    fout << s << "\n";
    fout << n - 1 << "\n";
    for( i=1; i<n; i++ )
        fout << sol[i].x << " " << sol[i].y << "\n";
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}