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

ifstream cin("apm.in");
ofstream cout("apm.out");

struct Edge {
    int u, v, val;
};
vector<Edge> vedge;

vector<vector<int>> graph;
vector<pair<int, int>> vres;


struct DSU {
    vector<int> vsize;
    vector<int> vid;
    
    void init(int n) {
        vsize.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            vid.push_back(i);
        }
    }

    int find(int u) {
        if (u == vid[u]) {
            return u;
        }
        return (vid[u] = find(vid[u]));
    }

    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return;

        if (vsize[u] < vsize[v]) {
            swap(u, v);
        }

        vid[v] = u;
        vsize[u] += vsize[v];
    }

};

queue<pair<int, int>> qp;


int main()
{
    int i, j, nr, u, v, n, m;
    int res = 0;
    DSU dsu = DSU();

    cin >> n >> m;

    dsu.init(n);
    graph.resize(n + 1);

    for (i = 0; i < m; i++) {
        cin >> u >> v >> nr;
        vedge.push_back({ u-1,v-1,nr });
    }

    sort(vedge.begin(), vedge.end(), [](Edge& e1, Edge& e2) {
        return e1.val < e2.val;
    });

    for (auto e : vedge) {
        if (pair<int,int>{ e.u,e.v } == pair<int, int>{2, 6}) {
            int r = 0;
        }
        if (dsu.find(e.u) != dsu.find(e.v)) {
            graph[e.u].push_back(e.v);
            graph[e.v].push_back(e.u);
            dsu.unite(e.u, e.v);
            vres.push_back({ e.u, e.v });
            res += e.val;
        }
    }

    //qp.push({ -1,0 });
    //while (!qp.empty()) {
    //    auto p = qp.front();
    //    qp.pop();
    //    for (auto v : graph[p.second]) {
    //        if (v != p.first) {
    //            vres.push_back({ p.second,v });
    //            qp.push({ p.second,v });
    //        }
    //    }
    //}

    cout << res << "\n";
    cout << vres.size() << "\n";
    for (auto p : vres) {
        cout << p.first+1 << " " << p.second+1 << "\n";
    }

    return 0;
}