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

#define Buffer 200001

using namespace std;

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

int n, m, sol;

int t[ Buffer ];

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 parent ( int x ) {

    int R = x;
    while ( t[R] != 0 )
        R = t[R];

    if ( x != R )
        t[x] = R;

    return R;
}

void Union(int x, int y) {
    t[ parent(y) ] = parent(x);
}

void Kruskal () {

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

    for ( unsigned int i = 0; i < Graph.size(); i++ ) {

        edge e = Graph[i];
        if ( parent( e.from ) != parent( e.to ) ) {
            Union( e.from, e.to );
            apm.push_back( e );
            sol += e.cost;
        }
    }
}

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 ();
    Kruskal ();
    write ();
    return 0;
}