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

using namespace std;

struct Dsf {
    int t;
    Dsf *parent;

    Dsf(int);
    Dsf *root();
    int get();
    void join(Dsf &);
};
Dsf::Dsf(int t = 0) {
    this->t = t;
    parent = NULL;
}
Dsf *Dsf::root() {
    Dsf *p = this;
    while(p->parent != NULL) {
        p = p->parent;
    }
    return p;
}
int Dsf::get() {
    return root()->t;
}
void Dsf::join(Dsf &other) {
    root()->parent = other.root();
}

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

struct Kruskal {
    int a, b, s;
    bool operator<(const Kruskal &) const;
};
bool Kruskal::operator<(const Kruskal &other) const {
    return s < other.s;
}

int main() {
    int n, m;
    f >> n >> m;

    vector<Kruskal> v(m+1);

    for(int i=1; i<=m; ++i)
        f >> v[i].a >> v[i].b >> v[i].s;

    sort(v.begin()+1, v.end());

    vector<bool> x(n+1, false);

    vector<Dsf> d(n+1, Dsf());
    for(int i=1; i<=n; ++i)
        d[i].t = i;

    int sum = 0;
    for(int i=1; i<=m; ++i) {
        int a = v[i].a;
        int b = v[i].b;
        int h1 = d[a].get();
        int h2 = d[b].get();
        if(h1 != h2) {
            sum += v[i].s;
            x[i] = true;
            d[a].join(d[b]);
        }
    }

    g << sum << "\n" << n-1 << "\n";
    for(int i=1; i<=m; ++i)
        if(x[i])
            g << v[i].a << " " << v[i].b << "\n";
}