#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

#define maxN 200005
#define PB push_back
#define MKP make_pair

int tata[maxN], H[maxN];
vector < pair < int, pair <int, int> > > lista;
vector < pair <int, int> > rsp;
int sol;


int root (int x)
{
	int R;
	
	for (R = x; tata[R] != R; R = tata[R]);
	for (int y; x != tata[x]; y = tata[x], tata[x] = R, x = y);
	
	return R;
}


void unite (int x, int y)
{
	int rx = root (x);
	int ry = root (y);
	
	if (H[rx] > H[ry])
		tata[ry] = rx;
	else tata[rx] = ry;
	
	if (H[rx] == H[ry]) ++ H[ry];
}


int main()
{
	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	while (M --)
	{
		int x, y, c;
		
		scanf ("%d %d %d", &x, &y, &c);
		
		lista.PB ( MKP ( c, MKP (x, y) ) );
	}
	
	sort (lista.begin(), lista.end());
	
	for (int i = 1; i <= N; ++ i) tata[i] = i;
	
	for (unsigned int i = 0; i < lista.size(); ++ i)
	{
		int x = lista[i].second.first, y = lista[i].second.second;
		
		if (root (x) == root (y)) continue;
		
		unite (x, y);
		sol += lista[i].first;
		rsp.PB ( MKP (x, y) );
	}
	
	printf ("%d \n%d \n", sol, rsp.size());
	
	for (unsigned int i = 0; i < rsp.size(); ++ i) printf ("%d %d\n", rsp[i].second, rsp[i].first);
	
	return 0;
}