#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200005
using namespace std;

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

struct node {
    int rang = 0;
    node *parent = nullptr;
};

struct edge {
    int x, y;
    int cost;
};

int n, m;
vector<node*> v(NMAX);
vector<edge> e;

node *findParent(node *a) {
    if (a->parent != nullptr) {
        a->parent = findParent(a->parent);
        return a->parent;
    }
    return a;
}

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

bool unesc(node *a, node *b) {
    a = findParent(a);
    b = findParent(b);
    if (a == b) {
        return false;
    }
    if (a->rang < b->rang) {
        a->parent = b;
    } else if (a->rang > b->rang) {
        b->parent = a;
    } else {
        b->parent = a;
        a->rang++;
    }
    return true;
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        v[i] = new node;
    }
    edge a;
    for (int i = 1; i <= m; ++i) {
        fin >> a.x >> a.y >> a.cost;
        e.push_back(a);
    }
    sort(e.begin(), e.end(), compare);
    int costF = 0;
    vector<edge> ans;

    for (int i = 0; i < m; ++i) {
        if (unesc(v[e[i].x], v[e[i].y])) {
            costF += e[i].cost;
            ans.push_back(e[i]);
        }
    }
    fout << costF << '\n' << ans.size() << '\n';
    for (int i = 0; i < ans.size(); ++i) {
        fout << ans[i].x << ' ' << ans[i].y << '\n';
    }
    return 0;
}