#include <iostream>
#include <fstream>
#include <tuple>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
const int N = 100001;
int n, m;
int tata[N];
int h[N];

struct Muchie
{
	int x, y, cost;
};

vector<Muchie> muchii;
vector<pair<int, int>> muchii_arb;

void initializare(int nod)
{
	tata[nod] = 0;
	h[nod] = 0;
}

int reprezentant(int nod)
{
	if (tata[nod] == 0)
	{
		return nod;
	}
	tata[nod] = reprezentant(tata[nod]);
	return tata[nod];
}

bool reuniune(int u, int v)
{
	int t1 = reprezentant(u);
	int t2 = reprezentant(v);
	if (t1 == t2)
	{
		return false;
	}
	if (h[t1] < h[t2])
	{
		tata[t1] = t2;
	}
	else
	{
		tata[t2] = t1;
		if (h[t1] == h[t2])
		{
			++h[t1];
		}
	}
	return true;
}

void afiseaza_arbore()
{
	for (auto [x, y] : muchii_arb)
	{
		fout << x << ' ' << y << '\n';
	}
}

int main()
{
	int nr_muchii_arb = 0;
	int cost_total = 0;
	fin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		initializare(i);
	}
	for (int i = 1; i <= m; ++i)
	{
		int x, y, z;
		fin >> x >> y >> z;
		muchii.push_back({x, y, z});
	}
	sort(muchii.begin(), muchii.end(), [](Muchie &m, Muchie &n) -> bool { return m.cost < n.cost; });
	for (auto m : muchii) // sortate
	{
		bool reunit = reuniune(m.x, m.y);
		if (reunit)
		{
			cost_total += m.cost;
			muchii_arb.push_back({m.x, m.y});
			if (++nr_muchii_arb >= n-1)
				break;
		}
	}
	fout << cost_total << '\n';
	fout << nr_muchii_arb << '\n';
	afiseaza_arbore();
	/*
	for (int i = 1; i <= n; ++i)
	{
		cout << "tata pentru " << i << ": " << tata[i] << '\n';
	}
	for (int i = 1; i <= n; ++i)
	{
		cout << "inaltime pentru " << i << ": " << h[i] << '\n';
	}
	*/
	fin.close();
	fout.close();
	return 0;
}