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

int n, m;
std::vector<std::vector<int>> graf;
struct nod
{
	int x, y;
	int cost;
};

std::vector<nod> muchii;

bool cmp(nod a, nod b)
{
	return a.cost < b.cost ? true : false;
}

void citire()
{
	std::ifstream f("apm.in");
	f >> n >> m;
	int x, y, cost;
	graf.resize(n + 1);
	muchii.resize(m + 1);
	for (int i = 1; i <= m; i++)
	{
		f >> x >> y >> cost;
		muchii[i].x = x;
		muchii[i].y = y;
		muchii[i].cost = cost;
	}
}

int grafuri[10];

void Kruskal()
{
	std::ofstream g("apm.out");
	int contor = 0;
	sort(muchii.begin() + 1, muchii.end(), cmp);
	contor = 1;
	graf[muchii[1].x].push_back(muchii[1].y);
	graf[muchii[1].y].push_back(muchii[1].x);
	grafuri[0] = 1;
	grafuri[muchii[1].x] = grafuri[muchii[1].y] = grafuri[0];
	grafuri[0]++;
	int sum = muchii[1].cost;
	for (int i = 2; i <= m; i++)
	{
		if (grafuri[muchii[i].x] == 0)//nu are garf
		{
			if (grafuri[muchii[i].y] == 0)//nu are graf
			{
				graf[muchii[i].x].push_back(muchii[i].y);
				graf[muchii[i].y].push_back(muchii[i].x);
				grafuri[muchii[i].x] = grafuri[muchii[i].y] = grafuri[0]++;//aloc graf
				contor ++;
				sum += muchii[i].cost;
			}
			else//are graf
			{
				graf[muchii[i].x].push_back(muchii[i].y);
				graf[muchii[i].y].push_back(muchii[i].x);
				grafuri[muchii[i].x] = grafuri[muchii[i].y];//bag in graf
				contor ++;
				sum += muchii[i].cost;
			}
		}
		else//primul nod e intr-un graf
		{
			if (grafuri[muchii[i].y] == 0)//nu are graf
			{
				graf[muchii[i].x].push_back(muchii[i].y);
				graf[muchii[i].y].push_back(muchii[i].x);
				grafuri[muchii[i].y] = grafuri[muchii[i].x];//bag in graf
				contor ++;
				sum += muchii[i].cost;
			}
			else//unesc grafuri
			{
				if (grafuri[muchii[i].x] != grafuri[muchii[i].y])
				{	
					graf[muchii[i].x].push_back(muchii[i].y);
					graf[muchii[i].y].push_back(muchii[i].x);
					contor++;
					sum += muchii[i].cost;
					int aux = grafuri[muchii[i].y];
					for (int j = 1; j <= n; j++)
					{
						if (grafuri[j] == aux)
						{
							grafuri[j] = grafuri[muchii[i].x];
						}
					}
				}
			}

		}



	}

	g << sum << "\n"<<contor<<"\n";
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < graf[i].size(); j++)
		{
			if (graf[i][j] < i)
			{
				g << i << " " << graf[i][j] << "\n";
			}
		}
	}
}

int main()
{
	citire();
	Kruskal();

	return 0;
}