/* Kruskal in O(m log m + m log *n) */

#include <bits/stdc++.h>
using namespace std;

class Edge {
    public:
    int a, b, cost;
};

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

    int n, m; cin >> n >> m;
    
    vector<Edge> edges(m);

    for(int i = 0; i < m; i += 1) {
        cin >> edges[i].a >> edges[i].b >> edges[i].cost;
        edges[i].a -= 1;
        edges[i].b -= 1; 
    }
    
    sort(edges.begin(), edges.end(), [&] (const Edge& x, const Edge& y) {
            return x.cost < y.cost;
    });

    vector<int> parent(n, 0);
    vector<int> depth(n, 0);

    for(int i = 0; i < n; i += 1) {
        parent[i] = i;
    }
    
    function<int(int)> rep = [&] (int x) {
        if(x == parent[x])
            return x;
        int root = rep(parent[x]);
        parent[x] = root; // Compresia drumului
        return root;
    };

    auto connected = [&] (int x, int y) {
        return rep(x) == rep(y);
    };

    auto unite = [&] (int a, int b) {
        a = rep(a);
        b = rep(b);

        if(depth[a] < depth[b]) { // Reuniune dupa rang
            parent[a] = b;
        } else {
            parent[b] = a;
        }

        if(depth[a] == depth[b]) { // Update-ul rangului
            depth[b] += 1;
        }
    };
    
    int total_cost = 0;
    vector<Edge> sol;

    for(auto edge : edges) {
        if(not connected(edge.a, edge.b)) {
            total_cost += edge.cost;
            sol.push_back(edge);
            unite(edge.a, edge.b);
        }
    }

    cout << total_cost << "\n";
    cout << sol.size() << "\n";

    for(auto edge : sol)
        cout << edge.a + 1 << " " << edge.b + 1 << "\n";
}