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

using namespace std;

#define maxN 200010
#define PB push_back
#define MKP make_pair
#define F first
#define S second

int tata[maxN], ans;
vector <pair <int, pair <int, int> > > Edges;
vector <pair <int, int> > sol;
vector <pair <int, int> > :: iterator it;


inline int root (int X)
{
	int R;
	
	for (R = X; R != tata[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);
	
	tata[ry] = rx;
}


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);
		
		Edges.PB ( MKP (c, MKP (x, y)) );
	}
	
	for (int i = 1; i <= N; ++ i) tata[i] = i;
	
	sort (Edges.begin(), Edges.end());
	
	for (unsigned int i = 0; i < Edges.size(); ++ i)
	{
		int nod1 = Edges[i].S.F, nod2 = Edges[i].S.S;
		
		if (root (nod1) == root (nod2)) continue;
		
		Unite (nod1, nod2);
		
		ans += Edges[i].F;
		sol.PB (MKP (nod1, nod2));
	}
	
	printf ("%d\n%d\n", ans, sol.size());
	for (it = sol.begin(); it != sol.end(); ++ it) printf ("%d %d\n", it -> F, it -> S);
	
	return 0;
}