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

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

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

int N, M;
vector<edge> E;

class DisjointSets
{
    static constexpr int NMAX = (int)(2e5 + 1);

    int t[NMAX], Size[NMAX];

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

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

    static inline void my_swap(int &a, int &b)
    {
        a = (a ^ b), b = (a ^ b), a = (a ^ b);

        return;
    }

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

        return;
    }

    inline bool Unify(int x, int y)
    {
        if (x == y)
            return 0;

        x = find(x), y = find(y);

        if (x == y)
            return 0;

        if (Size[y] > Size[x])
            my_swap(x, y);

        Size[x] += Size[y], Size[y] = 0;
        t[y] = x;

        return 1;
    }
} dsu;

static inline void read()
{
    f.tie(nullptr);

    f >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int x = 0, y = 0, u = 0;
        f >> x >> y >> u;

        E.push_back({u, {x, y}});
    }

    return;
}

int main()
{
    read();

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

    dsu.initialize(N);

    int total_cost = 0;

    vector<pair<int, int>> sol = {};

    for (auto &it : E)
        if (dsu.Unify(it.second.first, it.second.second))
            total_cost += it.first, sol.push_back(it.second);

    g << total_cost << '\n';
    g << (N - 1) << '\n';

    for (auto &it : sol)
        g << it.first << ' ' << it.second << '\n';

    return 0;
}