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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int NMAX = 200'001;

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

template < int SIZE >
class Disjoint {

private:

    vector < int > tree;

    void collapse(const int& root, int node) {
        while(node != root) {
            int aux = tree[node];
            tree[node] = root;
            node = aux;
        }
    }

public:

    Disjoint() {
        tree.resize(SIZE + 1, -1);
    }

    int Find(const int& node) {
        int root = node;

        while(tree[root] > 0)
            root = tree[root];

        collapse(root, node);

        return root;
    }

    void Union(int rootX, int rootY) {
        if(-tree[rootX] < -tree[rootY])
            swap(rootX, rootY);

        tree[rootX] = tree[rootX] + tree[rootY];
        tree[rootY] = rootX;
    }

};

int n, m;
vector < pair < int, int >  > G[NMAX];
vector < Edge > edges, sol;

int main() {

    f >> n >> m;

    while(m--) {
        int x, y, c;
        f >> x >> y >> c;

        G[x].push_back( { y, c } );
        G[y].push_back( { x, c } );
        edges.push_back({ x, y, c });
    }

    sort(edges.begin(), edges.end(),[](const Edge& a, const Edge& b) {
        return a.cost < b.cost;
    });

    Disjoint < NMAX > disjoint;
    int cnt = 0, cost = 0;

    for(Edge e : edges) {

        const int rootX = disjoint.Find(e.x);
        const int rootY = disjoint.Find(e.y);

        if(rootX != rootY) {
            sol.push_back(e);
            disjoint.Union(rootX, rootY);
            cnt++;
            cost += e.cost;
        }

        if(cnt == n - 1)
            break;
    }

    g << cost << '\n';
    g << (int) sol.size() << '\n';

    for(auto it : sol)
        g << it.x << ' ' << it.y << '\n';

    return 0;
}