#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int ls[400005][3];
int apm[400005][3];
int* rang[200005];
int lider[200005];
int conexiuni[200005];
int main()
{
	int n, m, muchii = 0, cost = 0;
	in >> n >> m;
	int k = 0;
	while (m--)
	{
		int v1, v2, c;
		in >> v1 >> v2 >> c;
		ls[k][0]=v1;
		ls[k][1] = v2;
		ls[k++ ][2]=c;
		
		lider[v1] = v1;
		lider[v2] = v2;
		rang[v1] = &lider[v1];
		rang[v2] = &lider[v2];
	}
	for (int i = 0; i < k-1; i++)
	{
		for (int j = i+1; j < k; j++)
		{
			if (ls[i][2] > ls[j][2]) {
			
				swap(ls[i][2], ls[j][2]);
				swap(ls[i][1], ls[j][1]);
				swap(ls[i][0], ls[j][0]);
			}
		}
	}
	
	for (int i = 0; i < k; i++)
	{
		int nod1=ls[i][0], nod2=ls[i][1];
		if (*rang[nod1] !=*rang[nod2])
		{
			apm[muchii][0] = ls[i][0];
			apm[muchii][1] = ls[i][1];
			apm[muchii++][2] = ls[i][2];
			cost += ls[i][2];
			
			if (conexiuni[lider[*rang[nod2]]] == 0)
			{
				rang[nod2] = &lider[*rang[nod1]];
				conexiuni[lider[*rang[nod1]]]++;
			}
			else {
				if (conexiuni[lider[*rang[nod1]]] == 0) {
					rang[nod1] = &lider[*rang[nod2]];
					conexiuni[lider[*rang[nod2]]]++;
				}
				else {
					lider[*rang[nod1]] = lider[*rang[nod2]];
				}
			}
			
			
			
			
			
		}


	}
	out << cost << "\n" << muchii << "\n";
	for (int i = 0; i < muchii; i++)
	{
		out << apm[i][0] << " " << apm[i][1] << "\n";
	}
	return 0;
}