#include<strstream>
#include <iostream>
#include <fstream>
#include <vector>
#include <conio.h>


using namespace std;

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

int n, m;
int parent[100];

struct nod
{
	int nod1, nod2, cost;
	nod *next;
}*start, *ultim;

void add(int x, int y, int c)
{
	if (start == NULL)
	{
		start = new nod;
		start->nod1 = x;
		start->nod2 = y;
		start->cost = c;
		start->next = NULL;
		ultim = start;
	}
	else
	{
		if (c < start->cost)
		{
			nod *p = new nod;
			p->next = start;
			start = p;
			p->nod1 = x;
			p->nod2 = y;
			p->cost = c;
		}
		else
		{
			if (c > ultim->cost)
			{
				nod*p = new nod;
				p->next = NULL;
				ultim->next = p;
				ultim = p;
				p->nod1 = x;
				p->nod2 = y;
				p->cost = c;
			}
			else
			{
				nod *p;
				p = start;
				while (p->next->cost < c)
					p = p->next;
				nod*q = new nod;
				q->next = p->next;
				p->next = q;
				q->nod1 = x;
				q->nod2 = y;
				q->cost = c;
			}
		}

	}
}

void sterge(nod *q)
{
	nod*p = start;
	nod*t = start;
	if (q == ultim)
	{
		while (p->next != ultim)
			p = p->next;
		p->next = NULL;
		delete q;
	}
	else
	{
		while (p != q)
		{
			t = p;
			p = p->next;
		}
		t->next = q->next;
		delete q;
	}
}

int varf(int x)
{
	if (x == parent[x])
		return x;
	return varf(parent[x]);
}

int main()
{
	int i, CostTot = 0, x, y, c, nr = 0, sem;
	f >> n >> m;
	for (i = 0; i < m; i++)
	{
		f >> x >> y >> c;
		add(x, y, c);
	}
	for (i = 1; i <= n; i++)
		parent[i] = i;
	nod *p = start;
	nod*q;
	while (nr < n - 1)
	{
		sem = 0;
		while(!sem && p )
		{
			if (varf(p->nod1) != varf(p->nod2))
			{
				nr++;
				CostTot += p->cost;
				parent[varf(p->nod1)] = p->nod2;
				sem = 1;
			}
			else
			{
				q = p;
				sterge(q);
			}
			p = p->next;
		}
	}
	g << CostTot << endl << nr << endl;
	for (i = 1, p = start; i <= nr && p != NULL; i++, p = p->next)
		g << p->nod1 << " " << p->nod2 << endl;
	return 0;
}