#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
struct Muchie {
    int x, y, c;
} a[400002];
int n, m, i, j, t[400002], tr[400002], r;
vector<pair<int, int>> v;

static inline int Tata(int a) {
    if(a == t[a]) return a;
    return (t[a] = Tata(t[a]));
}

static inline void Unire(int a, int b) {
    int ta = Tata(a);
    int tb = Tata(b);

    if(ta != tb) {
        if(tr[ta] < tr[tb]) t[ta] = tb;
        else {
            t[tb] = ta;
            if(tr[ta] == tr[tb]) tr[ta]++;
        }
    }
}

static inline bool Cmp(Muchie a, Muchie b) {
    return (a.c < b.c);
}

int main() {
    fin >> n >> m;
    for(i = 1; i <= m; i++) fin >> a[i].x >> a[i].y >> a[i].c;
    sort(a + 1, a + m + 1, Cmp);

    for(i = 1; i <= n; i++) {
        tr[i] = 1;
        t[i] = i;
    }

    for(i = 1; i <= m; i++) {
        int ta = Tata(a[i].x);
        int tb = Tata(a[i].y);

        if(ta != tb) {
            v.push_back({a[i].x, a[i].y});
            r += a[i].c;

            Unire(ta, tb);
        }
    }

    fout << r << "\n" << v.size() << "\n";
    for(auto it : v) fout << it.first << " " << it.second << "\n";

    return 0;
}