#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

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

const int MAXN = 200005;
int n, m;
vector<pair<int, int>> v[MAXN];
int comp;
int p[MAXN], l[MAXN];
int s;
vector<int> sol;

struct muchii {
    int a;
    int b;
    int c;
} c[MAXN];

bool srt(muchii a, muchii b) {
    return a.c < b.c;
}

int find(int k) {
    if (p[k] == k) {
        return k;
    }
    p[k] = find(p[k]);
    return p[k];
}

void reunion(int x, int y) {
    p[find(x)] = find(y);
}

int main() {

    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> c[i].a >> c[i].b >> c[i].c;
    }
    sort(c + 1, c + m + 1, srt);

    for (int i = 1; i <= n; ++i) {
        p[i] = i;
        l[i] = 1;
    }

    for (int i = 1; i <= m; ++i) {
        int x = c[i].a;
        int y = c[i].b;
        if (find(x) != find(y)) {
            reunion(x, y);
            s += c[i].c;
            sol.push_back(i);
        }
    }

    fout << s << '\n';
    fout << sol.size() << '\n';
    for (int i = 0; i < sol.size(); ++i) {
        fout << c[sol[i]].a << ' ' << c[sol[i]].b << '\n';
    }

    fout.close();
    return 0;
}