#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)
{
    while (cc[x] != 0)
    {
        x = cc[x];
    }
    return x;
}

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
            int parinte_to = get_parent(m.to);
            int parinte_from = get_parent(m.from);
            // daca amandoi sunt radacini
            #if 0
            if (parinte_from == parinte_to && parinte_from == 0)
            {
                cc[parinte_to] = parinte_from;
                edges_res.push_back(m);
            }
            #endif // 0
            else
            {
                // 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
                cc[parinte_to] = parinte_from;
                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;
}