//Arbore partial de cost minim
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

struct latura{
	int x,y,len;
};

bool cmp(latura a, latura b)
{
	return (a.len < b.len);
}

int H[100],T[100];

int root(int x)
{
	while(T[x]!=0) x=T[x];
	return x;
}

int main()
{
	vector <latura> L;
	int n, m;

	inFile >> n >> m;;

	latura l;

	for(int i=1; i<=m; i++)
	{
		inFile >> l.x >> l.y >> l.len;
		L.push_back(l);
	}

	
	
	sort(L.begin(),L.end(),cmp);

	int A[100], a=0;

	for(int i=1; i<=n; i++)
	{
		A[i]=i;
	}

	vector <latura> K;
/*
	for(int i=0; i<m; i++)
	{
		if(A[L[i].x] != A[L[i].y])
		{
			K.push_back(L[i]);
			int aux1=A[L[i].y], aux2=A[L[i].x];
			for(int j=1; j<=n; j++)
			{
				if(A[j] == aux1)
				{
					A[j] = aux2;
				}
			}
		}
	}
*/

	
	int cost=0;
	for(int i=0; i<m; i++)
	{
		int rx=root(L[i].x), ry=root(L[i].y);
		if(rx!=ry)
		{
			K.push_back(L[i]);
			cost+=L[i].len;
			if(H[rx]>H[ry]) T[ry]=rx;
			if(H[ry]>H[rx]) T[rx]=ry;
			if(H[rx]==H[ry]){ T[ry]=rx; H[rx]++; }
		}
	}


	outFile << cost << "\n" << n-1 << "\n";
	for(int i=0; i < n-1; i++)
	{
		outFile << K[i].x << " " << K[i].y << " " << K[i].len << "\n";
	}
}