#include <bits/stdc++.h>
#define DIM 100005
#define cost first
#define a second.first
#define b second.second
using namespace std;

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

int n, m, x, y, c, cost_sol;
pair< int, pair<int, int> > v[DIM];
pair<int, int> muchii[DIM];
int k;

int t[DIM];
int rx, ry, legaturi;

int radacina( int nod )
{
    while( t[nod] > 0 )
        nod = t[nod];
    return nod;
}

int main()
{
    in>>n>>m;
    for( int i = 1; i <= m; i++ )
    {
        in>>x>>y>>c;
        v[i] = make_pair( c, make_pair(x, y) );
    }

    sort( v + 1, v + m + 1 );

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

    for( int i = 1; i <= m; i++ )
    {
        rx = radacina( v[i].a );
        ry = radacina( v[i].b );

        if( rx != ry )
        {
            legaturi++;
            cost_sol += v[i].cost;

            if( t[rx] < t[ry] )
            {
                t[rx] += t[ry];
                t[ry] = rx;
            }
            else
            {
                t[ry] += t[rx];
                t[rx] = ry;
            }

            muchii[++k].first = v[i].a;
            muchii[k].second = v[i].b;
        }
    }

    out<<cost_sol<<"\n"<<legaturi<<"\n";
    for( int i = 1; i <= k; i++ )
        out<<muchii[i].first<<" "<<muchii[i].second<<"\n";

    return 0;
}