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

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

class Forest {
  private:
    vector<int> height;
    vector<int> father;

  public:
    Forest(int n) :
        height(n + 1),
        father(n + 1) { }

    int find(int x) {
        int root = x;
        while (father[root])
            root = father[root];

        int aux;
        while (father[x]) {
            aux = father[x];
            father[x] = root;
            x = aux;
        }
        return root;
    }

    void unite(int rootX, int rootY) {
        if (height[rootX] < height[rootY])
            father[rootX] = rootY;
        else {
            father[rootY] = rootX;
            if (height[rootX] == height[rootY])
                height[rootX]++;
        }
    }
};

struct Edge {
    int x, y, cost;
    Edge(int x, int y, int cost) :
        x(x), y(y), cost(cost) { }
    inline bool operator<(Edge e) const {
        return cost > e.cost;
    }
};

class Graph {
  private:
    int n;
    vector<Edge> edges;

  public:
    Graph(int n, int m) : n(n) {
        edges.reserve(m);
    }

    void addEdge(int x, int y, int cost) {
        edges.emplace_back(x, y, cost);
    }

    void kruskal() {
        Forest forest(n);
        make_heap(edges.begin(), edges.end());

        int cost = 0;
        vector<pair<int, int>> mst;
        mst.reserve(n - 1);

        for (int i = 1; i < n; ) {
            Edge edge = edges.front();
            pop_heap(edges.begin(), edges.end());
            edges.pop_back();

            int rootX = forest.find(edge.x);
            int rootY = forest.find(edge.y);

            if (rootX != rootY) {
                cost += edge.cost;
                mst.emplace_back(edge.x, edge.y);
                forest.unite(rootX, rootY);
                i++;
            }
        }

        fout << cost << '\n' << n - 1 << '\n';
        for (auto it : mst)
            fout << it.first << ' ' << it.second << '\n';
    }
};

int main() {
    int n, m;
    fin >> n >> m;

    Graph graph(n, m);
    for (int i = 0; i < m; i++) {
        int x, y, z; fin >> x >> y >> z;
        graph.addEdge(x, y, z);
    }
    graph.kruskal();

    fout.close();
    return 0;
}