#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define NMAX 200005
using namespace std;
struct muchie { int x,y,c; } t;
vector <muchie> p,r;
int s[NMAX];
int n,m;


class cmp
{
public:
	bool operator() (const muchie &A, const muchie &B) const
	{
		return (A.c > B.c);
	}
};

priority_queue < muchie , vector < muchie >, cmp > pq;


void read()
{
	scanf ("%d%d", &n,&m);
	
	for (int i=1;i<=m;i++)
	{
		scanf ("%d%d%d", &t.x,&t.y,&t.c);
		
		pq.push(t);
	}
}

void APM()
{
	long long S=0;
	int sw;
	
	t=pq.top();		pq.pop();			//avem prima muchie
	s[t.x]=s[t.y]=1;
	p.push_back(t);
	S+=t.c;
	
	for (int i=1;i<=n-2;i++)
	{
		sw=0;
		r.clear();
		
		do
		{
			t=pq.top();
		
			if (s[t.x]==s[t.y])			//daca muchia are ambele capete in arbore sau niciunul in arbore o eliminam din heap
				{
				if (!s[t.x])			//daca muchia e in`afara arborelui o vom introduce in heap ulterior
					r.push_back(t);
				pq.pop();
				continue;
			}
		
			p.push_back(t);
			pq.pop();
			s[t.x]=s[t.y]=1;
			S+=t.c;
			sw=1;
		}
		while (sw==0 && !pq.empty());
			
		for (int j=0;j<r.size();j++)	//reintroducerea muchiilor in heap
			pq.push(r[j]);
	}
	
	printf ("%lld\n%d\n", S, n-1);
	
	for (int i=0;i<p.size();i++)
		printf ("%d %d\n", p[i].x,p[i].y);
}
	

int main()
{
	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);
	
	read();
	
	APM();
	
	return 0;
}