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

#define NMax 200005
#define MMax 400005

using namespace std;

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

int N, M, rang[NMax], tata[NMax];
pair <int, int> sol[MMax];
int numar_muchii, cost_total;


struct arb
{
    int X, Y, COST;
}Muchie[MMax];

void Citire()
{
    fin >> N >> M;

    for(int i = 1; i <= M; ++ i)
        fin >> Muchie[i].X >> Muchie[i].Y >> Muchie[i].COST;

    fin.close();
}


bool _cost(arb m_1, arb m_2)
{
	return (m_1.COST < m_2.COST);
}

int cauta_tata(int nod)
{
    while(tata[nod] != nod)
        nod = tata[nod];

    return nod;
}

void uneste(int x, int y)
{
    if(rang[x] < rang[y])
        tata[x] = y;

    else if(rang[x] > rang[y])
        tata[y] = x;

    else if(rang[x] == rang[y])
    {
        tata[x] = y;
        rang[y] ++;
    }
}

void Kruskal()
{
	sort(Muchie + 1, Muchie + M + 1, _cost);

	for(int i = 1; i <= N; ++ i)
    {
		tata[i] = i;
		rang[i] = 1;
    }

	for(int i = 1; i <= M; ++ i)
    {
        int tatal_x = cauta_tata(Muchie[i].X);
        int tatal_y = cauta_tata(Muchie[i].Y);

        if(tatal_x != tatal_y)
        {
            uneste(tatal_x, tatal_y);

            numar_muchii ++;
            cost_total += Muchie[i].COST;

            sol[numar_muchii].first = Muchie[i].X;
            sol[numar_muchii].second = Muchie[i].Y;
        }
    }
}


void Afisare()
{
	fout << cost_total << '\n';
	fout << numar_muchii << '\n';

	for(int i = 1; i <= numar_muchii; ++ i, fout << '\n')
		fout << sol[i].first << ' ' << sol[i].second;

    fout.close();
}

int main()
{
    Citire();
    Kruskal();
    Afisare();

    return 0;
}