#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 400005

using namespace std;

int c[NMAX];

void citire(int &n, int &m, int x[], int y[], int indici[])
{
	ifstream fin("apm.in");
	fin >> n >> m;
	
	for (int i = 1; i <= m; ++i)
	{
		fin >> x[i] >> y[i] >> c[i];
		indici[i] = i;
	}
	
	fin.close();
}

const bool cmp(const int &i, const int &j)
{
	return (c[i] < c[j]);
}

int grupa(const int& i, int grup[])
{
	if (grup[i] == i) return i;
	grup[i] = grupa(grup[i], grup);
	return grup[i];
}


void reuniune(const int& i, const int& j, int grup[])
{
	grup[grupa(i, grup)] = grupa(j, grup);
}

void kruskal(int grup[], const int indici[], const int x[], const int y[], vector<int>& vans, const int& n, const int &m, int& ans)
{
	for (int i = 1; i <= n; i++)
		grup[i] = i;
	for (int i = 1; i <= m; ++i)
	{
		if (grupa(x[indici[i]], grup) != grupa(y[indici[i]], grup))
		{
			ans += c[indici[i]];
			reuniune(x[indici[i]], y[indici[i]], grup);
			vans.push_back(indici[i]);
		}
	}
}

void afisare(const int& ans, const int& n, vector<int>& vans, const int x[], const int y[])
{
	ofstream fout("apm.out");
	fout << ans << "\n";
	fout << n-1 << "\n";
	for (int i = 0; i < n-1; ++i)
		fout << x[vans[i]] << " " << y[vans[i]] << "\n";
}

int main()
{
	int m;
	int n;
	int ans = 0;
	int grup[NMAX];
	int indici[NMAX];
	int x[NMAX];
	int y[NMAX];
	
	vector<int> vans;
	
	citire(n, m, x, y, indici);
	sort(indici + 1, indici + m + 1, cmp);
	kruskal(grup, indici, x, y, vans, n, m, ans);
	afisare(ans, n, vans, x, y);
	return 0;
}