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

using namespace std;

#define PB push_back
#define MKP make_pair
#define NM 200005
#define inf 1000000000

int inside[NM], dmin[NM], fat[NM], ans, N, M;
vector <pair<int, int> > G[NM], muchii;

int main()
{
	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);
	
	scanf ("%d %d", &N, &M);
	
	for (int i = 1; i <= M; ++i)
	{
		int a, b, c;
		
		scanf ("%d %d %d", &a, &b, &c);
		
		G[a].PB(MKP(b, c));
		G[b].PB(MKP(a, c));
	}	
	
	for (int i = 1; i <= N; ++i) dmin[i] = inf;
	
	dmin[1] = 0;
	
	for (int m = 1; m <= N; ++m)
	{
		int best = inf, nbest;
		
		for (int i = 1; i <= N; ++i) 
			if (dmin[i] < best && !inside[i]) 
			{
				best = dmin[i];
				nbest = i;
			}
		
		inside[nbest] = 1;
		ans += best;
		//printf ("AAA %d\n", best);
		muchii.PB(MKP(fat[nbest], nbest));
		for (int i = 0; i < G[nbest].size(); ++i)
		{
			int nod = G[nbest][i].first;
			if (inside[nod]) continue;
			int cost = G[nbest][i].second;
			
			if (dmin[nod] > cost)
			{
				dmin[nod] = cost;
				fat[nod] = nbest;
			}	
		}	
	}	
	
	printf ("%d\n%d\n", ans, N-1);
	
	for (int i = 1; i < muchii.size(); ++i) printf ("%d %d\n", muchii[i].first, muchii[i].second);
	
	return 0;
}