#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

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

struct muchie
{
	int x, y, cost;
};

vector<muchie>a;
int n, m;
int t[200001];


bool compare(muchie a, muchie b)
{
	if (a.cost < b.cost)
		return 1;
	else return 0;
}

void citire()
{
	in >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int X, Y, C;
		in >> X >> Y >> C;
		a.push_back({ X,Y,C });
	}
	sort(a.begin(), a.end(), compare);
}

int Find(int k)
{
	if (t[k] == 0)
		return k;
	else
	{
		int x = Find(t[k]);
		t[k] = x;
		return x;
	}
}

int rang[200001];

void Union(int x, int y)
{
	if (x != y)
	{
		if (rang[x] > rang[y])
			t[y] = x;
		else
		{
			t[x] = y;
			if (rang[x] == rang[y])
				rang[y]++;
		}
	}
}

vector<pair<int, int>>apm;

void kruskal()
{
	int costmin = 0;
	for (auto it : a)
	{
		int fx=Find(it.x), fy=Find(it.y);
		if (fx != fy)
		{
			Union(fx, fy);
			costmin += it.cost;
			apm.push_back({ it.x,it.y });
		}
	}
	out << costmin << "\n" << apm.size() << "\n";
	for (auto it : apm)
		out << it.first << " " << it.second << "\n";
}

int main()
{
	citire();
	kruskal();
	return 0;
}