#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMAX 200005
using namespace std;
struct muchie { int x,y,c; } t;
vector <muchie> v,p;
int U[NMAX];
int cost,a,b,n,m;

void read()
{
	scanf ("%d%d", &n,&m);
	
	for (int i=1;i<=m;i++)
	{
		scanf ("%d%d%d", &t.x,&t.y,&t.c);
		
		v.push_back(t);
	}
	
	for (int i=1;i<=n;i++)
		U[i]=i;
}

bool static cmp (const muchie &a, const muchie &b)
{
	return (a.c < b.c);
}

int find(int nod)
{
	if (U[nod]==nod)
		return nod;
	
	//U[nod]=find(U[nod]);
	
	return find(U[nod]);
}

void Union(int a, int b)
{
	U[a]=b;
}

int main()
{
	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);
	
	read();
	
	sort (v.begin(), v.end(), cmp);
	
	for (int i=0;i<m;i++)
	{
		a=find(v[i].x);
		b=find(v[i].y);
		
		if (a!=b)
		{
			Union(a,b);
			
			cost+=v[i].c;
			p.push_back(v[i]);
		}
	}
	
	printf ("%d\n%d\n", cost, n-1);
	
	for (int i=0;i<n-1;i++)
		printf ("%d %d\n", p[i].x, p[i].y);
	
	return 0;
}