#include<bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int t[200005],c[200005];
void Union(int x, int y)
{
	t[y] = x;
	c[x] += c[y];
}
int Find(int x)
{
	int rad, y;
	rad = x;
	while (t[rad] != 0)
		rad = t[rad];
	while (x != rad)
	{
		y = t[x];
		t[x] = rad;
		x = y;
    }
	return rad;
}
struct muchie
{
   int x, y, cost, ok; // ok=1 daca muchia va face parte
// din APM
};

muchie a[200002];
int n, m;

bool Compara(const muchie A, const muchie B)
{
	return A.cost < B.cost;
}

int main()
{
    int i;
	fin >> n >> m;
	for (i=1;i<=m;i++)
		fin >> a[i].x >> a[i].y >> a[i].cost;
	sort(a + 1, a + m + 1, Compara);
int	costMinim = 0;
	int nrcc = n;
	for (i = 1; i <= m && nrcc > 1; i++)
	{
		int x = Find(a[i].x);
		int y = Find(a[i].y);
		if (x != y)
		{
			costMinim += a[i].cost;
			Union(x, y);
			a[i].ok = 1;
			nrcc--;
}
}
fout << costMinim<<"\n";
fout << (n - 1) << "\n";
for (i=1;i<=m;i++)
	if (a[i].ok == 1)
		fout << a[i].y << " " << a[i].x << "\n";
		return 0;
}