#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 2e5 + 2;

struct Tree {
    int a, b, cost;
    bool cut;
    Tree(int a, int b, int cost) : a(a), b(b), cost(cost), cut(false) {}
};

int n, m, cost, number;
vector <Tree> edges;
vector <int>  root[N_MAX], father(N_MAX);

void read() {
    ifstream fin("apm.in");

    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, cost;
        fin >> a >> b >> cost;
        edges.emplace_back(a, b, cost);
    }

    fin.close();
}

void unite(vector <int> &first, vector <int> &second) {
    vector <int> *x, *y;
    if (first.size() >= second.size())  {
        x = &first;
        y = &second;
    } else {
        x = &second;
        y = &first;
    }

    int ind = father[(*x)[0]];
    for (const auto &i : (*y)) {
        (*x).emplace_back(i);
        father[i] = ind;
    }

    (*y).clear();
}

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

void solve() {
    sort(edges.begin(), edges.end(), compare);

    for (int i = 1; i <= n; ++i) {
        root[i].emplace_back(i);
        father[i] = i;
    }

    for (auto &e : edges) {
        int a = e.a;
        int b = e.b;
        int c = e.cost;
        if (father[a] != father[b]) {
            unite(root[father[a]], root[father[b]]);
            e.cut = true;
            cost += c;
            ++number;
        }
    }
}

void write() {
    ofstream fout("apm.out");

    fout << cost << '\n' << number << '\n';
    for (const auto &e : edges) {
        if (e.cut) {
            fout << e.b << ' ' << e.a << '\n';
        }
    }

    fout.close();
}

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