#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#define N 200005
#define inf 1 << 30

using namespace std;

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

struct edge
{
    int a, b, c;
};

int n, m;
edge M[2*N];

int root[N], sz[N];

void read()
{
    int i;

    fin >> n >> m;

    for ( i = 1; i <= m; ++i )
        fin >> M[i].a >> M[i].b >> M[i].c;

    fin.close();
}

int Find( int x )
{
    int rx = x, aux;

    while ( rx != root[rx] ) rx = root[rx];

    while ( x != root[x] )
    {
        aux = root[x];
        root[x] = rx;
        x = aux;
    }

    return rx;
}

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

    if ( sz[rx] > sz[ry] )
    {
        root[y] = x;
        sz[x] += sz[y];
    }
    else
    {
        root[x] = y;
        sz[y] += sz[x];
    }
}

inline bool comp( edge X, edge Y )
{
    return X.c < Y.c;
}

void Kruskal()
{
    int i, x, y, cost = 0;
    vector < pair <int, int> > sol;

    sort( M + 1, M + m + 1, comp );

    for ( i = 1; i <= n; ++i )
    {
        root[i] = i;
        sz[i] = 1;
    }

    for ( i = 1; i <= m && sol.size() < n - 1; ++i )
    {
        x = Find( M[i].a );
        y = Find( M[i].b );

        if ( root[x] != root[y] )
        {
            Union( x, y );

            cost += M[i].c;
            sol.push_back( make_pair( M[i].a, M[i].b ) );
        }
    }

    fout << cost << '\n' << sol.size() << '\n';

    for ( i = 0; i < sol.size(); ++i )
        fout << sol[i].second << ' ' << sol[i].first << '\n';
}

int main()
{
    read();
    Kruskal();

    return 0;
}