#include <fstream>
#include <vector>
#include <algorithm>

#define Buffer 200001

using namespace std;

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

int n, m, sol;

bool included[ Buffer ];
bool usEdge[ 2 * Buffer - 1 ];

typedef struct {
    int from;
    int to;
    int cost;
} edge;

vector < edge > Graph;

vector < edge > apm;

bool compare ( edge a, edge b ) {
    if ( a.cost < b.cost )
        return true;
    return false;
}

void write () {

    fout << sol << "\n";

    fout << apm.size() << "\n"; // puteam afisa si n-1 ca doar aia e marimea unui arbore
    for ( unsigned int l = 0; l < apm.size(); l++ ) {
        fout <<  apm[l].from << " " << apm[l].to << "\n";
    }
}

int minConnectedEdge ( int l ) {

    while ( true ) {

        int from = Graph[l].from, to = Graph[l].to;
        //fout << from << " " << to << "\n";
        if ( usEdge[l] )
            l++;
        else if ( !included[ from ] && !included[to] )
            l++;
        else if ( included[ from ] && included[ to ] ) {
            l++;
            usEdge[l] = true;
        }
        else
            break;

        //fout << "bad\n";
    }
    //fout << "good\n";

    return l;
}

void Prims () {

    sort ( Graph.begin(), Graph.end(), compare );

    int l = 0, lo = 0;
    for ( int i = 1; i < n; i++ ) {

        if ( i > 1 )
            l = minConnectedEdge( lo );

        int from = Graph[l].from, to = Graph[l].to;

        sol += Graph[l].cost;
        apm.push_back( Graph[l] );
        included[ from ] = included[ to ] = true;
        usEdge[ l ] = true;

        while ( usEdge[ lo ] )
            lo++;

        l++;
    }
}

void read () {

    fin >> n >> m;

    int from, to, cost;
    for (int i = 1; i <= m; i++) {
        fin >> from >> to >> cost;

        edge e;
        e.from = from; e.to = to; e.cost = cost;
        Graph.push_back( e );
    }
}

int main()
{
    read ();
    Prims ();
    write ();
    return 0;
}