// PRIM O (M * logN)

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

using namespace std;

#define PB push_back
#define MKP make_pair
#define inf (1 << 30)
#define maxN 200005
#define tata(nod) (nod / 2)


int cost[maxN], v[maxN];
int pozH[maxN], H[maxN], dim; // Heap
int sol;
vector < pair <int, int> > lista[maxN], rsp;


void push (int nod)
{
	if (nod == 1) return;
	
	if (cost[H[tata(nod)]] <= cost[H[nod]]) return;
	
	swap (H[nod], H[tata (nod)]);
	swap (pozH[H[nod]], pozH[H[tata(nod)]]);
	
	push (tata (nod));
}


void pop (int nod)
{
	int nodmin = nod;
	int f1 = nod * 2, f2 = nod * 2 + 1;
	
	if (f1 <= dim && cost[H[f1]] < cost[H[nodmin]]) nodmin = f1;
	if (f2 <= dim && cost[H[f2]] < cost[H[nodmin]]) nodmin = f2;
	
	if (nod == nodmin) return;
	
	swap (H[nod], H[nodmin]);
	swap (pozH[H[nod]], pozH[H[nodmin]]);
	
	pop (nodmin);
}


int get_root ()
{
	int x = H[1];
	
	swap (H[1], H[dim]);
	swap (pozH[H[1]], pozH[H[dim]]);
	
	-- dim;
	pop (1);
	pozH[x] = 0;
	
	return x;
}


void apm_add (int nod)
{
	for (unsigned int i = 0; i < lista[nod].size(); ++ i)
	{
		int nod2 = lista[nod][i].first;
		int c = lista[nod][i].second;
		
		cost[nod2] = min (cost[nod2], c);
		
		if (cost[nod2] == c) v[nod2] = nod;
	}
}


void refresh_heap (int nod)
{
	for (unsigned int i = 0; i < lista[nod].size(); ++ i)
	{
		int nod2 = lista[nod][i].first;
		if (pozH[nod2]) push (pozH[nod2]);
	}
}


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[x]. PB ( MKP (y, c) );
		lista[y]. PB ( MKP (x, c) );
	}
	
	for (int i = 2; i <= N; ++ i) cost[i] = inf;

	apm_add (1);
	
	for (int i = 2; i <= N; ++ i)
	{
		H[++ dim] = i;
		pozH[i] = dim;
		push (dim);
	}
	
	for (int i = 1; i < N; ++ i)
	{
		int x = get_root ();
		
		apm_add (x);
		rsp.PB ( MKP (x, v[x]) );
		sol += cost[x];
		
		refresh_heap (x);
	}
	
	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;
}