#include <iostream>
#include <fstream>
#include <tuple>
#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;

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;
		++h[t2];
	}
	else
	{
		tata[t2] = t1;
		++h[t1];
	}
	return true;
}

void dfs(int nod)
{
	for (int i = 1; i <= n; ++i)
	{
		if (tata[i] == nod)
		{
			fout << nod << ' ' << i << '\n';
			dfs(i);
		}
	}
}

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