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

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

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

int n;
vector<edge> E = {};

class UnionFind
{
    vector<int> t;
    vector<int> Size;

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

        return (t[node] = find(t[node]));
    }

public:
    UnionFind(const int n)
    {
        t = vector<int>((n + 1), 0);
        for (int i = 1; i <= n; ++i)
            t[i] = i;

        Size = vector<int>((n + 1), 1);
        Size[0] = 0;

        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;
    }
};

void load_graph()
{
    int m = 0;

    f >> n >> m;

    int x = 0, y = 0, c = 0;
    for (int i = 1; i <= m; ++i)
    {
        f >> x >> y >> c,
            E.push_back({c, {x, y}});
    }

    return;
}

int main()
{
    load_graph();

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

    int total = 0;
    vector<PII> sol = {};

    UnionFind S(n);

    for (const edge &e : E)
        if (S.unify(e.second.first, e.second.second))
            total += e.first,
                sol.push_back(e.second);

    g << total << '\n'
      << (n - 1) << '\n';
    for (const PII &it : sol)
        g << it.first << ' ' << it.second << '\n';

    return 0;
}