#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <functional>


using LL = long long;
using ULL = int long long;

const std::string _problemName = "apm";

namespace std {
    std::ifstream fin(_problemName + ".in");
    std::ofstream fout(_problemName + ".out");
}

#define USE_FILES

#ifdef USE_FILES
#define cin fin
#define cout fout
#endif

struct SimpleEdge{
    int x, y;

    SimpleEdge(int x, int y) : x(x), y(y) {}
};

struct WeightedEdge : public SimpleEdge {
    int weight;

    WeightedEdge(int x, int y, int w) : SimpleEdge(x, y), weight(w) {}

    bool operator< (const WeightedEdge& other) {
        return weight < other.weight;
    }
};

struct Mst {

    Mst(int size) : weight(0), edges() {
        edges.reserve(size);
    }

    int weight;
    std::vector<SimpleEdge> edges;

    void push_back(const WeightedEdge& edge) {
        weight += edge.weight;
        edges.push_back(static_cast<SimpleEdge>(edge));
    }
};

struct Dsu {

public:

    Dsu(int size) : parents(size) {
        for (int idx = 0; idx < size; ++idx) {
            parents[idx] = idx;
        }
    }

    bool areSeparate(int x, int y) {
        return find(x) != find(y);
    }

    void join(int x, int y) {
        x = find(x);
        y = find(y);
        parents[x] = y;
    }

    int find(int x) {
        if (x == parents[x]) {
            return x;
        }
        parents[x] = find(parents[x]);
        return parents[x];
    }

private:

    std::vector<int> parents;
};

Mst buildMst(std::vector<WeightedEdge>&& edges, int n) {
    std::sort(edges.begin(), edges.end());

    Dsu dsu(n);
    Mst mst(n);

    for (auto edge : edges) {
        if (dsu.areSeparate(edge.x, edge.y)) {
            dsu.join(edge.x, edge.y);
            mst.push_back(edge);

            if (mst.edges.size() == n - 1) {
                break;
            }
        }
    }

    return mst;
}

int main() {

    int n, m;
    std::cin >> n >> m;

    std::vector<WeightedEdge> edges;
    edges.reserve(m);

    while (m--) {
        int x, y, c;
        std::cin >> x >> y >> c;
        --x, --y;

        edges.emplace_back(x, y, c);
    }

    Mst mst = buildMst(std::move(edges), n);

    std::cout << mst.weight << '\n';
    std::cout << mst.edges.size() << '\n';

    for (auto edge : mst.edges) {
        std::cout << edge.x + 1 << ' ' << edge.y + 1 << '\n';
    }
    std::cout << '\n';

    return 0;
}