#include<fstream>
#include<stdlib.h>
#define M1 200001
#define M2 400001

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie { int x,y,c; };
int n,m,l[M1];
muchie v[M2],h[M1];

int min(int x,int y) { if(x<y)return x;return y; }
int max(int x,int y) { if(x>y)return x;return y; }
int Find(int x) { if(x==l[x])return x; return l[x]=Find(l[x]); }
void Union(int x,int y)
{
	int px=Find(x);
	int py=Find(y);
	if(px<py) { l[py]=px; return;}
	l[px]=py;
}

int fcmp(void const *a,void const *b){ return ((muchie*)a)->c-((muchie*)b)->c; } 

int main()
{
	fin>>n>>m;
	for(int i=0;i<m;i++) fin>>v[i].x>>v[i].y>>v[i].c;
	int ms,c;
	ms=c=0;
	qsort(v,m,sizeof(v[0]),fcmp);
	for(int i=1;i<=n;i++) l[i]=i;
	int i=0;
	while(ms<n-1)
	{
		int px,py;
		do
		{
			px=Find(v[i].x); 
			py=Find(v[i].y);   
			if(px==py) i++; 
		}while(px==py);
		h[ms]=v[i];
		ms++;
		c+=v[i].c;
		Union(v[i].x,v[i].y);
	}
	fout<<c<<"\n"<<n-1<<"\n"; 
	for(int i=0;i<n-1;i++) fout<<h[i].x<<" "<<h[i].y<<endl; 

}