#include <cstdio>
#include <iostream>
#include <algorithm>
#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> > > muchii;
vector <pair <int , int> > solM;
int solCost;

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

void update (int x , int y)
{
	int rootX = root (x);
	int rootY = root (y);
	
	if (H[rootX] == H[rootY])
	{
		++H[rootX];
		
		tata[rootY] = rootX;
	}
	
	else if (H[rootX] < H[rootY])
		tata[rootX] = rootY;
	
	else tata[rootY] = rootX;
}

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