#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

const int nmax = 200001;
const int mmax = 400001;

ifstream f("apm.in");
ofstream g("apm.out");

struct edge
{
	int a, b, c;
	edge(int d, int e, int f) :a(d), b(e), c(f) {};

};


vector<edge> M;
vector < pair<int, int>> MuchiiNoi;
int n, m;

int TT[nmax], H[nmax];

bool compare(edge a, edge b)
{
	return a.c < b.c;
}


void citire()
{
	f >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		TT[i] = i;
		H[i] = 1;
	}

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		f >> a >> b >> c;
		edge nou(a, b, c);
		M.push_back(nou);
	}

	sort(M.begin(), M.end(), compare);
	
}

void unite(int a, int b)
{
	if (H[a] > H[b])
	{
		TT[b] = a;
		H[a]++;
	}

	if (H[b] > H[a])
	{
		TT[a] = b;
		H[b]++;

	}
	if (H[b] == H[a])
	{
		TT[a] = b;
		H[b]++;
	}
}

int find(int x)
{
	while (TT[x] != x)
		x = TT[x];
	return x;
}


int main()
{

	citire();
	int cost = 0;
	for (int i = 0; i < m; i++)
	{
		if (find(M[i].a) != find(M[i].b))
		{
			unite(find(M[i].a), find(M[i].b));
			cost += M[i].c;
			pair<int, int> B;
			B.first = M[i].a;
			B.second = M[i].b;
			MuchiiNoi.push_back(B);	
		}
	}

	g << cost << "\n";
	g << MuchiiNoi.size() << "\n";

	for (int i = 0; i < MuchiiNoi.size(); i++)
	{
		g << MuchiiNoi[i].first << " " << MuchiiNoi[i].second << "\n";

	}




	return 0;

}