#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie {
    int x, y, c;
} p[200002];
int n, m, i, j, r;
int t[200002], tr[200002];
queue<pair<int, int>> q;

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

static inline void unire(int ta, int tb) {
    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) {
    if(a.c < b.c) return true;
    else return false;
}

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

    for(i = 1; i <= n; i++) {
        tr[i] = 1;
        t[i] = i;
    }
    sort(p + 1, p + m + 1, cmp);


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

        if(ta != tb) {
            r += p[i].c;
            q.push({p[i].x, p[i].y});

            unire(ta, tb);
        }
    }

    fout << r << "\n" << q.size() << "\n";
    while(!q.empty()) {
        fout << q.front().first << " " << q.front().second << "\n";
        q.pop();
    }

    return 0;
}