#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream g("apm.out");

const int NMAX = 200005;
int tata[NMAX], sz[NMAX];
vector<pair<int, pair<int, int>>> v;
vector<pair<int, int>> res;

int find(int x) {
    if (tata[x] == 0) {
        tata[x] = x;
        sz[x] = 1;
    }
    if (x == tata[x])
        return x;
    return tata[x] = find(tata[x]);;
}

void uni(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return;
    if (sz[b] > sz[a])
        swap(a, b);
    sz[a] += sz[b];
    tata[b] = a;
}

int main() {

    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        v.push_back(make_pair(c, make_pair(x, y)));
    }
    sort(v.begin(), v.end());
    int total = 0;
    for (auto m : v) {
        int cost = m.first, x = m.second.first, y = m.second.second;
        if (find(x) != find(y)) {
            total += cost;
            uni(x, y);
            res.push_back(make_pair(x, y));
        }
    }
    g << total << '\n' << res.size() << '\n';
    for (auto m : res) {
        g << m.first << ' ' << m.second << '\n';
    }


    return 0;
}