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

using namespace std;

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

class UnionFind
{
    vector < int > t, 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),
            size = vector < int > ((n + 1), 1);

            size[0] = 0;

            for(int i = 1; i <= n; ++i)
                t[i] = i;
        }

        bool unify (const int a, const int b)
        {
            if(a == b)
                return false;

            int x = find(a), y = find(b);

            if(x == y)
                return false;

            if(size[x] > size[y])
                size[x] += size[y],
                size[y] = 0,

                t[y] = x;
            else
                size[y] += size[x],
                size[x] = 0,

                t[x] = y;

            return true;
        }

        ~UnionFind () = default;
};

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

int main ()
{
    int n = 0, m = 0;
    f >> n >> m;

    UnionFind *d = new UnionFind(n);

    vector < edge > e(m);
    for(int i = 0; i < m; ++i)
    {
        int x = 0, y = 0, cost = 0;
        f >> x >> y >> cost;

        e[i] = {cost, {x, y}};
    }

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

    int answer = 0, cnt = 0;
    vector < PII > sol(n - 1);

    for(const edge &p : e)
        if(d -> unify(p.second.first, p.second.second))
            answer += p.first, sol[(cnt++)] = p.second;

    assert(cnt == (n - 1));

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

    delete d;

    return 0;
}