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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int MMAX = 400000;
const int NMAX = 200000;
struct muchie
{
    int nod1, nod2, cost;
    bool operator < (const muchie &a)const{
        return cost<a.cost;
    }
};
vector <muchie> muchii;
vector <muchie>muchii_finale; /// aici vom avea raspunsul problemei
int h[NMAX+5], t[NMAX+5]; ///h - vectorul de inaltimi, iar t- vectorul de tati
int FindSet(int x)
{
    while(x !=t[x])
        x =t[x];
    return x;
    ///acesta functie nu face si compresia drumurilor
}
void UnionSet(int x, int y)
{
    ///x si y sunt radacinile celor 2 arbori
    if(h[x]==h[y])
    {
        h[x]++;
        t[y] = x;
    }
    else
    {
        if(h[x]>h[y])
            t[y] = x;
        else
            t[x] = y;
    }
}

int main()
{
    int n, m, i, cost, nod1, nod2, tx, ty;
    muchie aux;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        t[i] = i;
        h[i] = 1;
    }
    for(i=1;i<=m;i++)
    {
        fin>>nod1>>nod2>>cost;
        aux.nod1 = nod1;
        aux.nod2 = nod2;
        aux.cost = cost;
        muchii.push_back(aux);
    }
    int cost_total=0;
    sort(muchii.begin(), muchii.end());
    for(i=0;i<m;i++)
    {
        tx = FindSet(muchii[i].nod1);
        ty = FindSet(muchii[i].nod2);
        if(tx!=ty)
        {
          cost_total = cost_total + muchii[i].cost;
          UnionSet(tx, ty);
          muchii_finale.push_back(muchii[i]);
        }
    }
    fout<<cost_total<<"\n";
    fout<<muchii_finale.size()<<"\n";
    for(i=0;i<muchii_finale.size();i++)
        fout<<muchii_finale[i].nod1<<" "<<muchii_finale[i].nod2<<"\n";

    return 0;
}