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

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

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

static constexpr int nMAX = ((int)(2e5) + 4);

int n;
vector<PIII> edges = {};

class UnionFind
{
    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 initialize(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;
            return true;
        }

        t[x] = y, size[y] += size[x], size[x] = 0;
        return true;
    }
};

static void read()
{
    int m = 0;

    f.tie(nullptr);
    f >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int u = 0, v = 0, w = 0;
        f >> u >> v >> w;

        edges.push_back({w, {u, v}});
    }

    return;
}

int main()
{
    read();

    UnionFind S;
    S.initialize(n);

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

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

    for (const PIII &it : edges)
        if (S.unify(it.second.first, it.second.second))
            answer += it.first, solution.push_back(it.second);

    g << answer << '\n'
      << (int)solution.size() << '\n';

    for (const PII &it : solution)
        g << it.first << ' ' << it.second << '\n';

    return 0;
}