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

using namespace std;

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

const int NMAX = 200005;
int nodes, edges;
int suma = 0;

struct edge{
    int x, y, cost;
    edge(int x, int y, int cost) : x(x), y(y), cost(cost) {}
};

vector <edge> Graf;
vector <pair <int, int>> Sol;
int tati[NMAX];

void InitTati(int x){
    for (int i = 1; i <= x; ++i) {
        tati[i] = i;
    }
}

void citire(){
    in >> nodes >> edges;

    InitTati(nodes);

    for (int i = 0; i < edges; ++i) {
        int a, b, c;
        in >> a >> b >> c;
        Graf.emplace_back (a, b, c);
    }
}

bool cmp(edge a, edge b){
    return a.cost < b.cost;
}

int getRoot(int x){
    if(x == tati[x])
        return x;
    tati[x] = getRoot (tati[x]);
    return tati[x];
}

bool areUnited(int x, int y){
    return getRoot(x) == getRoot(y);
}

void unite(int x, int y){
    tati[getRoot (x)] = getRoot (y);
}

void solve(){
    sort(Graf.begin (), Graf.end (), cmp);

    for (int i = 0; i < Graf.size (); ++i) {
        edge e = Graf[i];

        if(!areUnited(e.x, e.y)){
            unite(e.x, e.y);
            Sol.push_back ({e.x, e.y});
            suma += e.cost;
        }
    }
}

int main() {

    citire();
    solve();
    out << suma << "\n";
    out << Sol.size () << "\n";
    for (int i = 0; i < Sol.size (); ++i) {
        out << Sol[i].first << " " << Sol[i].second << "\n";
    }
    return 0;
}