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

const int NMAX = 1e5;

struct Edge {
    int x, y, cost;
};

bool cmp(Edge a, Edge b) {
    return a.cost < b.cost;
}

struct DSU {
    vector<int> h, p;
    DSU(int n) {
        h.resize(n + 1);
        p.resize(n + 1);
        for(int i = 1; i <= n; i++) {
            h[i] = 1;
            p[i] = i;
        }
    }

    int Find(int x) {
        int r = x;
        while(r != p[r]) {
            r = p[r];
        }
        int y = x;
        while(y != r) {
            int t = p[y];
            p[y] = r;
            y = t;
        }
        return r;
    }

    void Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        if(x != y) {
            if(h[x] < h[y]) {
                p[x] = y;
            } else {
                if(h[y] < h[x]) {
                    p[y] = x;
                } else {
                    p[y] = x;//p[x] = y si h[y]++;
                    h[x]++;
                }
            }
        }
    }

};

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m;
    f >> n >> m;
    DSU d(n);
    vector<Edge> v;
    for(int i = 1; i <= m; i++) {
        int x, y, c;
        f >> x >> y >> c;
        v.push_back({x, y, c});
    }
    sort(v.begin(), v.end(), cmp);
    int sum = 0;
    vector<Edge> sol;
    for(auto it : v) {
        if(d.Find(it.x) != d.Find(it.y)) {
            d.Union(it.x, it.y);
            sum += it.cost;
            sol.push_back(it);
        }
    }
    g << sum << '\n';
    g << sol.size() << '\n';
    for(auto it : sol) {
        g << it.x << ' ' << it.y << '\n';
    }
    return 0;
}