#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<list>
using namespace std;
struct edge {
	int x, y, w;
};

int n, m;
vector<edge> E;
list<edge> APM;


bool comp(edge e1, edge e2)
{
	return e1.w < e2.w;
}

void citire()
{
	ifstream fin("apm.in");
	fin >> n >> m;
	E.resize(m);
	for (int i = 0; i < m; i++)
		fin >> E[i].x >> E[i].y >> E[i].w;
	fin.close();

}

int* t,*h;
void init()
{
	t = new int[n + 1];
	h = new int[n + 1];
	for (int i = 1; i <= n; i++)
		t[i] = 0, h[i] = 0; 

}

int find(int x)
{
	if (t[x] == 0) return x;
	return find(t[x]); 
}

void Union(int x, int y)
{
	x = find(x), y = find(y);
	if(h[x]>h[y])
	{
		t[y] = x; return;
	}
	t[x] = y;
	if (h[x] == h[y]) h[y]++;
}




int main()
{
	citire();
	sort(E.begin(), E.end(),comp);

	int sum = 0,sel=0;
	init();
	for (edge e : E)
	{
		if (find(e.x) != find(e.y))
		{
			APM.push_back(e);
			sum += e.w;
			sel++; 
			Union(e.x, e.y);

		}
		if (sel == n - 1) break; 
	}

	ofstream fout("apm.out");
	fout << sum << endl;
	fout << sel << endl; // fout<<n-1;
	for (edge e : APM)
	{
		fout << e.x << " " << e.y<<endl;
	}
	fout.close();
	
	return 0;

}