#include <bits/stdc++.h>
#define Nmax 200005
using namespace std;

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

struct muchie
{
    int x, y;
    int cost;

    friend bool operator > ( muchie, muchie );
};

bool operator > ( muchie a, muchie b )
{
    return a.cost > b.cost;
}
void Kruskal ( );

priority_queue < muchie, vector < muchie >, greater<muchie> > H;

int n, m, costmin, nrsel;
int t[Nmax], h[Nmax];
muchie sel[Nmax];

void read ( );
void afisare ( );

int Find ( int x );

void Union ( int x, int y );


int main()
{
    read ( );

    Kruskal ( );

    afisare ( );
}

void afisare ( )
{
    fout << costmin << '\n' << n-1 <<'\n';

    for ( int i = 0 ; i < n-1; i++ )
        fout << sel[i].x << ' ' << sel[i].y << '\n';
}

void Kruskal ( )
{
    muchie a;

    int nrsel = 0;
    int c1, c2;

    while ( nrsel < n-1 )
    {
        a = H.top();
        H.pop();

        c1 = Find ( a.x );
        c2 = Find ( a.y );

        if ( c1 != c2 )
        {
            sel[nrsel++] = a;
            Union( c1, c2 );

            costmin += a.cost;
        }
    }
}

void Union ( int x, int y )
{
    int rx = Find ( x );
    int ry = Find ( y );

    if ( h[rx] > h[ry] )
        t[ry] = rx;
    else
    {
        t[rx] = ry;

        if ( h[ry] == h[rx] )
            h[ry]++;
    }
}

int Find ( int x )
{
    int rad = x, y;
    while ( t[rad] )
        rad = t[rad];

    while ( t[x] )
    {
        y = t[x];
        t[x] = rad;
        x = y;
    }

    return rad;
}

void read ( )
{
    muchie a;

    fin >> n >> m;

    for ( int i = 0 ; i < m; i++ )
    {
        fin >> a.x >> a.y >> a.cost;
        H.push(a);
    }
}