#include<cstdio>
#include<algorithm>
#define N 1<<18
#define M 1<<19
#define in freopen("apm.in","r",stdin)
#define out freopen("apm.out","w",stdout)
using namespace std;
typedef struct muchie
{
	int x,y,c;
};
muchie a[M];
int n,m,cf,nrf,t[N];
bool util[M];
bool comp(const muchie &A,const muchie &B)
{
	if(A.c<B.c)
		return true;
	return false;
}
void read()
{
	in;
	out;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
	sort(a+1,a+m+1,comp);
}
int compact(int nod)
{
	if(t[nod]==0) return nod;
	return t[nod]=compact(t[nod]);
}
void solve()
{
	int rx,ry;
	for(int i=1;i<=m;i++)
	{
		rx=compact(a[i].x);
		ry=compact(a[i].y);
		if(rx!=ry)
		{
			if(t[a[i].x])
				t[a[i].y]=rx;
			else t[a[i].x]=ry;
			util[i]=true;
			cf+=a[i].c;
			nrf++;
		}
	}
}
void afis()
{
	printf("%d\n%d\n",cf,nrf);
	for(int i=1;i<=m;i++)
		if(util[i])
			printf("%d %d\n",a[i].x,a[i].y);
}
int main()
{
	read();
	solve();
	afis();
	return 0;
}