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

using namespace std;

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

const int maxn = 2e5;
const int maxm = 4e5;
struct muchie {
    int u, v, cost;
    
    muchie(int u = 0, int v = 0, int cost = 0) {
        this->u = min(u, v);
        this->v = max(u, v);
        this->cost = cost;
    }
    bool operator<(const muchie &a) const {
        return cost < a.cost;
    }
    friend istream& operator>>(istream &is, muchie &target) {
        int u, v, cost;
        is >> u >> v >> cost;
        target = muchie(u, v, cost);
        return is;
    }
    friend ostream& operator<<(ostream &os, const muchie &target) {
        os << target.u << ' ' << target.v;
        return os;
    }
};
muchie edges[maxm];
int root[maxn + 1];

int findRoot(int id) {
    if (root[id] == id)
        return id;
    return root[id] = findRoot(root[id]);
}

void unite(int x, int y)  {
    int rx = findRoot(x);
    int ry = findRoot(y);
    root[rx] = ry;
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++)
        fin >> edges[i];
    sort(edges, edges + m);
    for (int i = 0; i < m; i++)
        root[i] = i;
    
    int cost = 0;
    vector<muchie> arbore;
    for (int i = 0; i < m; i++) {
        int ru = findRoot(edges[i].u);
        int rv = findRoot(edges[i].v);
        if (ru != rv) {
            unite(ru, rv);
            cost += edges[i].cost;
            arbore.push_back(edges[i]);
        }
    }

    fout << cost << '\n' << n - 1 << '\n';
    for (muchie elem: arbore)
        fout << elem << '\n';

    return 0;
}