#include <bits/stdc++.h>
#define DIM 100005
using namespace std;

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

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

int t[DIM], legaturi, sol;
vector< pair<int, int> > sol_muchii;

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

void adauga_muchie( int a, int b, int poz )
{
    int ra = radacina(a);
    int rb = radacina(b);

    if( ra == rb )
        return;

    if( t[ra] < t[rb] )
    {
        t[ra] += t[rb];
        t[rb] = ra;
        return;
    }

    if( t[ra] > t[rb] )
    {
        t[rb] += t[ra];
        t[ra] = rb;
    }

    sol += muchii[poz].first;
    legaturi++;
    sol_muchii.push_back( make_pair(a, b) );
}

int main()
{
    in>>n>>m;

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

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

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

    for( int i = 1; i <= m; i++ )
        if( legaturi < n - 1 )
            adauga_muchie( muchii[i].second.first, muchii[i].second.second, i );

    out<<sol<<"\n";
    for( pair<int, int> i : sol_muchii )
        out<<i.first<<" "<<i.second<<"\n";
}