#include<fstream>
#include<cstdio>
#define MaxN 100001
#define MaxM 200001

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int n,m,nr,cost,ans[MaxN],T[MaxN],rg[MaxN];

struct muchie{
		int x,y,cost;
		};
muchie e[MaxM];

struct cmp{
	bool operator() ( const muchie &a , const muchie &b )
		{
			return a.cost < b.cost;
		}
};

int find_root(int x)
{
	int rad,y;
	rad = x;
	while( T[rad] != rad )
		rad = T[rad];
	while( T[x] != x )
		{
			y = T[x];
			T[y] = rad;
			x = y;
		}
	return rad;
}

void union1(int x , int y )
{
	if( rg[x] <= rg[y] )
		T[x] = y;
		else
		T[y] = x;
	if( rg[x] == rg[y] )
		++rg[y];
}

int main(void)
{
	f >> n >> m ;
	int i;
	for( i = 1 ; i <= n ; i++ )
		T[i] = i,rg[i] = 1;
	for( i = 1 ; i <= m ; i++ )
		f >> e[i].x >> e[i].y >> e[i].cost;
	sort(e+1,e+m+1,cmp());
	nr = 0;
	i = 1;
	while( nr < n-1 )
		{
			if( find_root(e[i].x) != find_root(e[i].y) )
				{
					ans[++nr] = i;
					union1(e[i].x,e[i].y);
					cost += e[i].cost;
				}
			i++;
		}
	g << cost << '\n' << n-1 << '\n';
	for( i = 1 ; i < n ; i++ )
		g << e[ans[i]].x << ' ' << e[ans[i]].y << '\n';
	f.close();
	g.close();
	return 0;
}