#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

class muchie
{
public:
    int from;
    int to;
    int cost;
    muchie(int _from, int _to, int _cost):
        from(_from), to(_to), cost(_cost)
    {

    }
};

int n,m;
vector<muchie> edges;
int cc_curenta = 1;
int cc[200005];
vector<muchie> edges_res;

int get_parent(int x)
{
    vector<int> met_on_the_way;
    while (cc[x] != 0)
    {
        met_on_the_way.push_back(x);
        x = cc[x];
    }
    for (auto el: met_on_the_way)
        cc[el] = x;
    return x;
}

pair<int, int> get_parent_and_depth(int x)
{
    vector<int> met_on_the_way;
    int h = 0;
    while (cc[x] != 0)
    {
        met_on_the_way.push_back(x);
        h++;
        x = cc[x];
    }
    for (auto el: met_on_the_way)
        cc[el] = x;
    return {x,h};
}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x,y,d;
        f >> x >> y >> d;
        edges.push_back({x,y,d});
    }

    for (int i = 1; i <= n; i++)
        cc[i] = -1;

    sort(edges.begin(), edges.end(), [](muchie& m1, muchie& m2){return m1.cost < m2.cost;});

    for (auto& m: edges)
    {
        // o muchie a carei noduri nu se afla in apm
        if (cc[m.from] == -1 && cc[m.to] == -1)
        {
            // il facem root
            cc[m.from] = 0;
            // from va fi tatal lui to
            cc[m.to] = m.from;
            edges_res.push_back(m);
        }
        // daca amandoua au mai fost intalnite
        else if (cc[m.from] != -1 && cc[m.to] != -1)
        {
            // daca au acelasi parinte nu le putem conecta
            pair<int,int> info_to = get_parent_and_depth(m.to);
            pair<int,int> info_from = get_parent_and_depth(m.from);
            int parinte_to = info_to.first;
            int parinte_from = info_from.first;
            int height_to = info_to.second;
            int height_from = info_from.second;
            // daca amandoi sunt radacini

            {
                // daca au acelasi parinte nu le legam
                if (parinte_from == parinte_to)
                    continue;
                // il facem pe parintele lui m.to copil al lui m.from
                if (height_from > height_to)
                    cc[parinte_to] = parinte_from;
                else
                    cc[parinte_from] = parinte_to;
                edges_res.push_back(m);
            }
        }
        else
        {
            // daca una e deja in apm si cealalta nu
            if (cc[m.from] != -1)
            {
                // daca from este deja in apm, facem to copil al rootului lui from
                int parinte_from = get_parent(m.from);
                cc[m.to] = parinte_from;
            }
            else
            {
                int parinte_to = get_parent(m.to);
                cc[m.from] = parinte_to;
            }
            edges_res.push_back(m);
        }
    }

    int suma = 0;
    for (auto& m: edges_res)
        suma += m.cost;
    g << suma << '\n';
    g << edges_res.size() << '\n';
    for (auto& m: edges_res)
        g << m.from << ' ' << m.to << '\n';

    return 0;
}