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

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

struct edge {
    int x, y, w;
};
bool cmp (edge a, edge b) {
    return a.w < b.w;
}
int const nmax = 200000;
std::vector <edge> muchii;
std::vector <edge> ans;

int p[nmax + 5];
int r[nmax + 5];
int cntTree;

struct DSU {
    void init (int x) {
        cntTree = x;
        for (int i = 1; i <= x; i++) {
            p[i] = i;
            r[i] = 1;
        }
    }
    int find (int x) {
        if (p[x] == x)
            return x;
        return p[x] = find(p[x]);
    }
    void unite (int x, int y) {
        x = find (x);
        y = find (y);
        cntTree--;
        if (r[x] < r[y])
            std::swap (x, y);
        p[y] = x;
        if (r[x] == r[y])
            r[x]++;
    }
};


int main() {
    DSU UnionFind;
    int n, m;
    fin >> n >> m;
    UnionFind.init(n);
    for (int i = 1; i <= m; i++) {
        int x, y, w;
        fin >> x >> y >> w;
        muchii.push_back({x, y, w});
    }
    std::sort (muchii.begin(), muchii.end(), cmp);
    int poz = 0, cost = 0;
    for (; poz < m && cntTree > 1; poz++) {
        if (UnionFind.find (muchii[poz].x) != UnionFind.find (muchii[poz].y)) {
            UnionFind.unite (muchii[poz].x, muchii[poz].y);
            cost += muchii[poz].w;
            ans.push_back(muchii[poz]);
        }
    }
    fout << cost << "\n";
    int lim = ans.size();
    fout << lim << "\n";
    for (int i = 0; i < lim; i++)
        fout << ans[i].x << " " << ans[i].y << "\n";
    return 0;
}