#include <fstream>
#include <vector>
#include <bitset>

using namespace std;
const int NMAX = 200000,
          MMAX = 400000;

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

int n, m, minedge[NMAX], foundEdge;
long long rez;
bitset<MMAX> viz;

struct muchie
{
    int u, v, cost;
} Mc[MMAX];

vector<muchie> sol;

struct DSU
{
    int sef[NMAX], nr_comp;

    void init(int n)
    {
        nr_comp = n;
        for(int i = 0; i < n; i++)
            sef[i] = i;
    }

    int Find(int i)
    {
        if(sef[i] == i)
            return i;
        return sef[i] = Find(sef[i]);
    }

    void Union(int i, int j)
    {
        if((i = Find(i)) != (j = Find(j)))
        {
            nr_comp--;
            sef[j] = i;
        }
    }
} dsu;

void citire()
{
    f >> n >> m;
    for(int i = 0; i < m; i++)
    {
        f >> Mc[i].u >> Mc[i].v >> Mc[i].cost;
        Mc[i].u--;
        Mc[i].v--;
    }
}

void resetComps()
{
    for(int i = 0; i < n; i++)
        minedge[i] = -1;
}

///este muchia a mai buna decat muchia b?
bool better(int a, int b)
{
    if(b == -1)
        return 1;
    return Mc[a].cost < Mc[b].cost;
}

void procesare_muchii()
{
    int i, ru, rv;
    for(i = 0; i < m; i++)
    {
        if(!viz[i]) ///daca n-am folosit muchia deja
        {
            ru = dsu.Find(Mc[i].u);
            rv = dsu.Find(Mc[i].v);
            if(ru != rv)
            {
                if(better(i, minedge[ru]))
                    minedge[ru] = i;
                if(better(i, minedge[rv]))
                    minedge[rv] = i;
            }
        }
    }
}

void procesare_componente()
{
    for(int i = 0; i < n; i++) ///trecem prin fiecare componenta
    {
        if(minedge[i] != -1 && viz[minedge[i]] == 0)
        {
            dsu.Union(Mc[minedge[i]].u, Mc[minedge[i]].v);
            sol.push_back({Mc[minedge[i]].u, Mc[minedge[i]].v, Mc[minedge[i]].cost});
            rez += Mc[minedge[i]].cost;
            viz[minedge[i]] = 1;
            foundEdge = 1;
        }
    }
}

void Boruvka()
{
    dsu.init(n);
    rez = 0;
    foundEdge = 1;
    while(dsu.nr_comp > 1 && foundEdge) /// cat timp nu e arbore si mai putem face ceva
    {
        foundEdge = 0;
        resetComps();
        procesare_muchii();
        procesare_componente();
    }
    //
    g << rez << '\n' << sol.size() << '\n';
    for(auto &x : sol)
        g << x.u + 1 << ' ' << x.v + 1 << '\n';
}

int main()
{
    citire();
    Boruvka();
    f.close();
    g.close();
    return 0;
}