#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

class muchie
{
public:
	int x,y,c;
	bool operator <(muchie &rhs);
};

bool muchie::operator <(muchie &rhs)
{
	if (c<rhs.c)
	{
		return true;
	}
	return false;
}

vector<muchie> a;
muchie aux;
int root[20];

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

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	int m,n,i,cost,it;

	scanf("%d%d",&n,&m);
	for (i=0;i<m;i++)
	{
		scanf("%d%d%d",&aux.x,&aux.y,&aux.c);
		a.push_back(aux);
	}
	sort(a.begin(),a.end());
	for (i=1;i<=n;i++)
	{
		root[i] = i;
	}
	i = 0;
	cost = 0;
	it = 0;
	vector<muchie> sol;
	while (i<n-1)
	{
		if (find(a[it].x) != find(a[it].y))
		{
			root[find(a[it].x)] = find(a[it].y);
			cost+=a[it].c;
			i++;
			aux.x = a[it].x;
			aux.y = a[it].y;
			sol.push_back(aux);
		}
		it++;
	}
	printf("%d\n",cost);
	printf("%d\n",n-1);
	for (i=0;i<sol.size();i++)
	{
		printf("%d %d\n",sol[i].x,sol[i].y);
	}
	return 0;
}