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

using namespace std;

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

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

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

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;
	
	int cost_sol = 0;
	
	for (int t = 1 ; t <= N ; ++t)
	{
		int costcur = INF , nodcur;
		
		for (int i = 1 ; i <= N ; ++i)
			if (cost[i] < costcur && !viz[i])
			{
				costcur = cost[i];
				nodcur = i;
			}
		
		viz[nodcur] = true;
		cost_sol += costcur;
		
		
		sol.PB (MKP (tata[nodcur] , nodcur));
		
		
		for (unsigned int i = 0 ; i < lista[nodcur].size () ; ++i)
		{
			int nodd = lista[nodcur][i].first;
			int costt = lista[nodcur][i].second;
			
			if (viz[nodd]) continue;
			if (cost[nodd] <= costt) continue;
			
			cost[nodd] = costt;
			tata[nodd] = 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;
}