#include <bits/stdc++.h>
#define Nmax 200005
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

const int INF = Nmax;
long long int N, M, k, sum;

vector < pair < int, int > > v[Nmax];
bitset < Nmax > b;

int pos[Nmax], h[Nmax], sol[Nmax], d[Nmax];

void read ( );
void Prim ( );

int main()
{
    read ( );

    Prim ( );

    fout << sum << '\n' << N-1 << '\n';

    for ( int i = 2; i <= N; i++ )
        fout << i << ' ' << sol[i] << '\n';

    return 0;
}

void downheap ( int p )
{
    int c;

    while ( p <= k )
    {
        c = p;

        if ( c << 1 <= k )
        {
            c <<= 1;

            if( c+1 <= k && d[h[c]] > d[h[c+1]] )
                c++;

        }

        else
            return;

        if ( d[h[p]] > d[h[c]] )
        {
            pos[h[p]] = c;
            pos[h[c]] = p;

            swap ( h[p], h[c] );

            p = c;
        }

        else return ;
    }
}

void upheap ( int c )
{
    int p;

    while ( c > 1 )
    {
        p = c >> 1;

        if ( d[h[c]] < d[h[p]] )
        {
            pos[h[p]] = c;
            pos[h[c]] = p;

            swap ( h[p], h[c] );

            c = p;
        }

        else
            return;
    }
}

void Prim ( )
{
    int minn, node, cost, lng;

    for ( int i = 1; i <= N; i++ )
        d[i] = INF, pos[i] = i, h[i] = i;

    d[1] = 0;
    k = N;

    for ( int i = 1 ; i < N ; i++ )
    {
        minn = h[1];
        sum += d[minn];
        b[minn] = 1;
        h[1] = h[k];
        pos[h[1]] = 1;
        k--;
        downheap(1);

        lng = v[minn].size();

        for ( int i = 0; i < lng; i++ )
        {
            node = v[minn][i].first;
            cost = v[minn][i].second;

            if ( b[node] == 0 && d[node] > cost )
            {
                d[node] = cost;

                sol[node] = minn;

                upheap(pos[h[node]]);
            }
        }
    }

    sum += d[h[1]];
}

void read ( )
{
    int x, y, c;

    fin >> N >> M;

    for ( int i = 1 ; i <= M; i++ )
    {
        fin >> x >> y >> c;

        v[x].push_back ( make_pair ( y, c ) );
        v[y].push_back ( make_pair ( x, c ) );
    }
}