#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 P[NMax];
list<muchie> sol;

int find(int x)
{
    if (x==P[x]) return x;
    P[x]=find(P[x]);
    return P[x];
}

int solve()
{
	int i,ret=0;
	sort(m,m+M);
	for (i=1;i<=N;++i)
		P[i]=i;
	for (i=0;i<M;++i) if ( find(m[i].x)!=find(m[i].y) )
	{
	    P[find(m[i].x)]=P[find(m[i].y)];
	    sol.push_back(m[i]);
	    ret+=m[i].c;
	}
	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;
}