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

using namespace std;


#define maxN 200005
#define INF 0x3f3f3f3f
#define PB push_back
#define MKP make_pair


int N , M , cost[maxN] , tata[maxN];
bool viz[maxN];

int H[maxN] , pozH[maxN] , dim;


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


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


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


int heap_min ()
{
	int nod = H[1];
	
	swap (H[1] , H[dim]);
	swap (pozH[H[1]] , pozH[H[dim]]);
	
	--dim;
	pop (pozH[H[1]]);
	
	return nod;
}


void make_heap ()
{
	for (int i = 1 ; i <= N ; ++i)
	{
		H[++dim] = i;
		pozH[i] = dim;
		
		push (dim);
	}
}


int main ()
{
	freopen ("apm.in" , "r" , stdin);
	freopen ("apm.out" , "w" , stdout);
	
	scanf ("%d %d" , &N , &M);
	
	int a , b , c;
	
	for (int i = 1 ; i <= M ; ++i)
	{
		scanf ("%d %d %d" , &a , &b , &c);
		
		lista[a].PB (MKP (b , c));
		lista[b].PB (MKP (a , c));
	}
	
	
	for (int i = 2 ; i <= N ; ++i)
		cost[i] = INF;
	
	
	make_heap ();
	
	int cost_sol = 0;
	
	for (int t = 1 ; t <= N ; ++t)
	{
		int best_node = heap_min ();
		
		viz[best_node] = true;
		cost_sol += cost[best_node];
		
		
		sol.PB (MKP (tata[best_node] , best_node));
		
		
		for (unsigned int i = 0 ; i < lista[best_node].size () ; ++i)
		{
			int nodcur = lista[best_node][i].first;
			int costcur = lista[best_node][i].second;
			
			if (viz[nodcur]) continue;
			if (cost[nodcur] <= costcur) continue;
			
			cost[nodcur] = costcur;
			tata[nodcur] = best_node;
			
			push (pozH[nodcur]);
		}
	}
	
	printf ("%d\n" , cost_sol);
	printf ("%d\n" , sol.size () - 1);
	
	for (unsigned int i = 1 ; i < sol.size () ; ++i)
		printf ("%d %d\n" , sol[i].first , sol[i].second);
	
	return 0;
}