#include<stdio.h>
#include<algorithm>
#include<fstream>

using namespace std;
#define N 200010
#define M 400010

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

struct graph
{
	int x,y;
	short int c;
};



int n,m;
graph v[M];
int ind[M],t[N],gr[N];
int cost,rez[N];

void read()
{
	fin>>n>>m;
	for(int i=0; i<m; ++i)
	{   fin>>v[i].x>>v[i].y>>v[i].c;
		ind[i]=i;
	}
}
int find(int x)
{
	int r=x;
	for(; t[r]!=r; r=t[r])
		;
	while(t[x]!=x)
	{
		int aux=t[x];
		t[x]=r;
		x=aux;
	}
	return r;
}
void reuniune(int x,int y)
{
	if(gr[x]<gr[y])
		t[x]=y;
	else
		t[y]=x;
	if(gr[x]==gr[y])
		++gr[x];
}
bool compar(const int &x,const int &y)
{
	return (v[x].c<v[y].c);
}
void solve()
{
	for(int i=1; i<=n; ++i)
	{
		t[i]=i;
		gr[i]=1;
	}
	sort(ind,ind+m,compar);
	int n1=n-1;
	for(int i=0; i<m && rez[0]!=n1; ++i)
	{
		int nod=ind[i];
		if(find(v[nod].x)!=find(v[nod].y))
		{
			cost+=v[nod].c;
			rez[++rez[0]]=nod;
			reuniune(find(v[nod].x),find(v[nod].y));
		}
	}
}
void print()
{
	fout<<cost<<endl<<n-1<<endl;
	for(int i=1; i<=rez[0]; ++i)
        fout<<v[rez[i]].x<<" "<<v[rez[i]].y<<endl;

}
int main()
{

	read();
	solve();
	print();
	fin.close();
	fout.close();
	return 0;
}