#include <stdio.h>
#include <list>
#include <algorithm>
#define NMax 200010
using namespace std;

const char IN[]="apm.in",OUT[]="apm.out";

struct muchie{
	int x,y,c;
	bool operator<(muchie const &b) const{
		return c<b.c;
	}
} m[NMax*2];

int N,M;
int st[NMax];
list<int> a[NMax];
list<muchie> sol;

int solve()
{
	int i,ret=0;
	sort(m,m+M);
	for (i=1;i<=N;++i)
		a[i].push_back(i),
		st[i]=i;
	for (i=0;i<M;++i) if (st[m[i].x]!=st[m[i].y])
	{
		int x=st[m[i].y];
		int y=st[m[i].x];
		if ( a[x].size() > a[y].size() ) swap(x,y);
		ret+=m[i].c;
		sol.push_back(m[i]);
		for (list<int>::iterator it=a[x].begin();it!=a[x].end();++it)
		{
			st[*it]=st[y];
			a[y].push_back(*it);
		}
		a[x].clear();
	}
	return ret;
}

int main()
{
	int i,x,y,r;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	for (i=0;i<M;++i)
		scanf("%d%d%d",&m[i].x,&m[i].y,&m[i].c);
	fclose(stdin);
	
	r=solve();
	
	freopen(OUT,"w",stdout);
	printf("%d\n",r);
	printf("%d\n",sol.size());
	for (list<muchie>::iterator it=sol.begin();it!=sol.end();++it)
		printf("%d %d\n",it->x,it->y);
	fclose(stdout);
	
	return 0;
}