#include <iostream>
#include <fstream>

using namespace std;

#define Nmax 200005

#define Father(i) i/2
#define LeftSon(i) 2*i
#define RightSon(i) 2*i+1

int X[Nmax], Y[Nmax], C[Nmax];
int TATA[Nmax], RANG[Nmax];
int MX[Nmax], MY[Nmax];

int N, M, COST, selected;

void read()
{
    ifstream f("apm.in");

    f >> N >> M;

    for ( int i = 1; i <= M; ++i )
            f >> X[i] >> Y[i] >> C[i];

    f.close();
}

void DownHeap( int m, int poz )
{
    int k = poz, j;

    do
    {
        j = k;

        if ( LeftSon(j) <= m && C[LeftSon(j)] < C[k] )  k = LeftSon(j);
        if ( RightSon(j) <= m && C[RightSon(j)] < C[k]) k = RightSon(j);

        if ( j != k )
        {
            swap( C[j], C[k] );
            swap( X[j], X[k] );
            swap( Y[j], Y[k] );
        }

    } while( j != k );
}

void UpHeap( int poz )
{
    int k = poz, j;

    do
    {
        j = k;

        if ( j > 1 && C[Father(j)] > C[k] ) k = Father(j);

        if ( j != k )
        {
            swap( C[j], C[k] );
            swap( X[j], X[k] );
            swap( Y[j], Y[k] );
        }

    } while( j != k );
}

void MakeHeap()
{
    for ( int i = M/2; i; i-- )
            DownHeap( M, i );
}

void pop()
{
    C[1] = C[M];
    X[1] = X[M];
    Y[1] = Y[M];

    DownHeap( M, 1 );

    M--;
}

void HeapSort()
{
    for ( int i = M; i >= 2; i-- )
    {
        swap( C[1], C[i] );
        swap( X[1], X[i] );
        swap( Y[1], Y[i] );

        DownHeap( i - 1, 1 );
    }
}

int FIND( int x )
{
    int R, y;

    for ( R = x; TATA[R] != R; R = TATA[R] );

    for ( ; TATA[x] != x; )
    {
        y = TATA[x];
        TATA[x] = R;
        x = y;
    }

    return R;
}

void UNION( int x, int y )
{
    if ( RANG[x] > RANG[y] )
            TATA[y] = x;
    else
            TATA[x] = y;

    if ( RANG[x] == RANG[y] )
            RANG[y]++;

}

void init()
{
    for ( int i = 1; i <= N; ++i )
            TATA[i] = i,
            RANG[i] = 1;
}

void Kruskal()
{
    int m = M;

    for ( int i = 1; i <= m && selected < N-1; i++ )
    {
        int x = X[1];
        int y = Y[1];
        int c = C[1];

        pop();

        int fx = FIND( x );
        int fy = FIND( y );

        if ( fx != fy )
        {
            UNION( fx, fy );

            COST += c;

            selected++;

            MX[selected] = x;
            MY[selected] = y;
        }
    }
}

void print()
{
    ofstream g("apm.out");

    g << COST << "\n" << selected << "\n";

    for ( int i = 1; i <= selected; ++i )
            g << MX[i] << " " << MY[i] << "\n";

    g.close();
}

int main()
{
    read();
    MakeHeap();
    init();
    Kruskal();
    print();

    return 0;
}