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

using namespace std;

const int N = 200001;
int n, m, cost_total, nrm_arb;

int c[N];
int h[N];

struct Muchie
{
	int u, v, cost;
};

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

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

void initializeaza(int nod)
{
	c[nod] = nod;
	h[nod] = 0;
}

int repr(int nod)
{
	return c[nod];
}

bool reuniune(int u, int v)
{
	int r1 = repr(u);
	int r2 = repr(v);
	if (r1 == r2)
	{
		return false;
	}
	if (h[r1] < h[r2])
	{
		for (int i = 1; i <= n; ++i)
		{
			if (repr(i) == r2)
			{
				c[i] = r1;
			}
		}
	}
	else
	{
		for (int i = 1; i <= n; ++i)
		{
			if (repr(i) == r1)
			{
				c[i] = r2;
			}
		}
		if (h[r1] == h[r2])
		{
			++h[r1];
		}
	}
	return true;
}

int main()
{
	fin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		initializeaza(i);
	}
	for (int i = 1; i <= m; ++i)
	{
		int x, y, cost;
		fin >> x >> y >> cost;
		muchii.push_back({x, y, cost});
	}
	sort(muchii.begin(), muchii.end(), [](Muchie &a, Muchie &b) -> bool { return a.cost < b.cost; });
	for (auto [u, v, cost] : muchii)
	{
		bool reunit = reuniune(u, v);
		if (reunit)
		{
			cost_total += cost;
			muchii_arb.push_back({u, v});
			++nrm_arb;
			if (nrm_arb >= n-1)
				break;
		}
	}
	fout << cost_total << '\n';	
	fout << nrm_arb << '\n';
	for (auto [u, v] : muchii_arb)
	{
		fout << u << ' ' << v << '\n';
	}
	fin.close();
	fout.close();
	return 0;
}