#include <iostream>
#include <fstream>
#include <algorithm>

#define Nmax 200005
#define Mmax 400005

using namespace std;

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

int vf, muchii;

int Tata[Nmax], Dimensiune[Nmax];

pair < int, int > Salvare_Elemente[Nmax];
int ct_salvare_elemente;

long long Suma;

struct elemente
{
    int x, y, cost;
} V[Mmax];

inline int Sort_elemente(elemente x, elemente y)
{
    return x.cost < y.cost;
}

inline int Find(int x)
{
    if(x != Tata[x])
        Tata[x] = Find(Tata[x]);
    return Tata[x];
}
void Unire(int x, int y, int cost)
{
    x = Find(x);
    y = Find(y);

    if(Dimensiune[x] < Dimensiune[y])
    {
        Dimensiune[y] += Dimensiune[x];
        Suma += cost;
        Tata[x] = y;
    }
    else
    {
        Dimensiune[x] += Dimensiune[y];
        Suma += cost;
        Tata[y] = x;
    }
}

int main()
{
    fin >> vf >> muchii;
    for(int i = 1; i <= muchii; ++ i)
    {
        Tata[i] = i;
        Dimensiune[i] = 1;
    }
    for(int i = 1; i <= muchii; ++ i)
    {
        fin >> V[i].x >> V[i].y >> V[i].cost;
    }
    sort(V + 1, V + muchii + 1, Sort_elemente);
    for(int i = 1; i <= muchii; ++ i)
    {
        int tata_x = Find(V[i].x);
        int tata_y = Find(V[i].y);

        if(tata_x != tata_y)
        {
            Unire(V[i].x, V[i].y, V[i].cost);
            Salvare_Elemente[++ ct_salvare_elemente] = {V[i].x, V[i].y};
            //Suma += cost;
        }
    }
    fout << Suma << "\n";
    fout << ct_salvare_elemente << "\n";
    for(int i = 1; i <= ct_salvare_elemente; ++ i)
        fout << Salvare_Elemente[i].second << " " << Salvare_Elemente[i].first << "\n";
    return 0;
}