#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

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

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


int root (int x)
{
	int R, y;
	
	for (R = x; tata[R] != R; R = tata[R]);
	
	for ( ; tata[x] != x; x = y)
	{
		y = tata[x];
		tata[x] = R;
	}
	
	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 nod1 = lista[i].second.first;
		int nod2 = lista[i].second.second;
		
		if (root (nod1) == root (nod2)) continue;
		
		sol += lista[i].first;
		
		unite (nod1, nod2);
		
		rsp.PB ( MKP (nod2, nod1) );
	}
	
	printf ("%d\n%d\n", sol, N - 1);
	
	for (unsigned int i = 0; i < rsp.size(); ++ i)
		printf ("%d %d \n", rsp[i].first, rsp[i].second);
	
	return 0;
}