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

using namespace std;

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

int N, M, ARB[200005];
pair <int, int> sol[400005];
int numar_muchii, cost_total;


struct Muchie
{
    int X, Y, COST;
}vec[400005];

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

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

    fin.close();
}


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

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

	for(int i = 1; i <= N; ++ i)
		ARB[i] = i;

	for(int i = 1; i <= M; ++ i)
		if(ARB[vec[i].X] != ARB[vec[i].Y])
		{
			numar_muchii ++;
			cost_total += vec[i].COST;

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

			int Varf = ARB[vec[i].Y];
			int Baza = ARB[vec[i].X];

			for(int j = 1; j <= N; ++ j)
				if(ARB[j] == Varf)
					ARB[j] = Baza;
		}
}


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;
}