#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
using PII = pair<int, int>;
using edge = pair<int, PII>;

class UnionFind
{
    static constexpr int nMAX = ((int)(2e5) + 1);

    int t[nMAX], Size[nMAX];

private:
    int find(const int node)
    {
        if (node == t[node])
            return node;
        return (t[node] = find(t[node]));
    }

public:
    void init(const int n)
    {
        for (int i = 1; i <= n; ++i)
            t[i] = i, Size[i] = 1;

        return;
    }

    bool unify(int x, int y)
    {
        if (x == y)
            return false;
        x = find(x), y = find(y);

        if (x == y)
            return false;

        if (Size[x] > Size[y])
            t[y] = x, Size[x] += Size[y], Size[y] = 0;
        else
            t[x] = y, Size[y] += Size[x], Size[x] = 0;

        return true;
    }
};
UnionFind S;

vector<edge> list_edges = {};

static inline void read()
{
    ifstream f("apm.in");
    f.tie(nullptr);

    int n = 0, m = 0;
    f >> n >> m;

    S.init(n);

    int u = 0, v = 0, c = 0;

    for (int i = 1; i <= m; ++i)
        f >> u >> v >> c, list_edges.push_back({c, {u, v}});

    f.close();

    return;
}

int main()
{
    read();

    sort(list_edges.begin(), list_edges.end());

    int answer = 0;
    vector<edge> solution = {};

    for (const edge &e : list_edges)
        if (S.unify(e.second.first, e.second.second))
            answer += e.first, solution.push_back(e);

    ofstream g("apm.out");
    g.tie(nullptr);

    g << answer << '\n'
      << (int)solution.size() << '\n';
    for (const edge &e : solution)
        g << e.second.first << ' ' << e.second.second << '\n';

    g.close();

    return 0;
}