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

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

typedef pair < int , pair < int, int > > pi;

vector < pi > v;
vector < pair < int, int > > sol;

int t[Nmax], grad[Nmax], cost, lng, n, m;

void read ( );
bool cmp ( pi, pi );

void Kruskal ( );
int cauta ( int x );

int main ( )
{
    read ( );

    Kruskal ( );

    lng = sol.size();

    fout << cost << '\n' << lng << '\n';

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

int cauta ( int x )
{
    int root, cx = x;
    while ( x != t[x] )
        x = t[x];

    root = x;

    x = cx;

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

    return root;
}

void Kruskal ( )
{
    int root1, root2;

    sort ( v.begin(), v.end(), cmp );

    for ( int i = 1; i <= n; i++ )
        t[i] = i;

    vector < pi > :: iterator it;

    for ( it = v.begin(); it != v.end(); it++ )
    {
        root1 = cauta ( it->second.first );
        root2 = cauta ( it->second.second );

        if ( root1 == root2 )
            continue;

        else
        {
            sol.push_back ( mp(it->second.first, it->second.second) );

            cost += it->first;

            if ( grad[root1] >= grad[root2] )
            {
                t[root2] = root1;

                grad[root1]++;
            }

            else
            {
                t[root1] = root2;

                grad[root2]++;
            }
        }
    }
}

bool cmp ( pi a, pi b )
{
    if ( a.first < b.first )
        return 1;
    return 0;
}

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

    fin >> n >> m;

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

        v.push_back( mp (c, mp (x,y)) );
        v.push_back( mp (c, mp (y,x)) );
    }
}