#include <bits/stdc++.h>

using namespace std;

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3");

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
    int parinte, copil ,cost;
};

muchie muchii[4000005];
int nrNoduri, nrMuchii, nrMuchiiMin;
long long costMin;
int parinte[200005];
vector<pair<int, int>> sol;

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

void citire()
{
    fin >> nrNoduri >> nrMuchii;
    for(int i = 1; i <= nrMuchii; i++)
    {
        fin >> muchii[i].parinte >> muchii[i].copil >> muchii[i].cost;
    }
    sort(muchii+1, muchii+nrMuchii+1, cmp);
}

int gasesteParinte(int n)
{
    int aux = n, anterior;
    while (parinte[aux]!= 0){
        aux = parinte[aux];
    }
    anterior = n;
    while(parinte[anterior] != 0)
    {
        anterior = parinte[n];
        parinte[n] = aux;
    }
    return aux;
}

bool formeazaCiclu(int parintee, int copil)
{
    if(gasesteParinte(parintee) == gasesteParinte(copil))
        return true;
    return false;
}

void unire(int copil, int parintee)
{
    int radacinaCopil = gasesteParinte(copil);
    int radacinaParinte = gasesteParinte(parintee);
    parinte[radacinaCopil] = radacinaParinte;
}

void kruskal()
{
    for(int i = 1; i <= nrMuchii; i++)
    {
        if(!formeazaCiclu(muchii[i].parinte, muchii[i].copil))
        {
            costMin += muchii[i].cost;
            nrMuchiiMin++;
            sol.push_back(make_pair(muchii[i].parinte, muchii[i].copil));
            unire(muchii[i].copil, muchii[i].parinte);
        }
    }
}

void afis()
{
    fout << costMin << '\n' << nrMuchiiMin << '\n';
    for(int i = 0; i < sol.size(); i++)
    {
        fout << sol[i].second << ' ' << sol[i].first << '\n';
    }
}

int main()
{
    citire();
    kruskal();
    afis();
    
    return 0;
}