using namespace std;
#include<fstream>
#include<algorithm>
ifstream eu("apm.in");
ofstream tu("apm.out");
#define Nmax 4000005
pair <int,int> P[Nmax];
int N,M,cost,TT[Nmax],k;
struct Edge 
{
	int x,y,c;
	
};
Edge V[Nmax];
bool cmp(Edge a,Edge b)
{
	return a.c<b.c;
}

void read()
{
	eu>>N>>M;
	for(int i=1;i<=M;i++)
		eu>>V[i].x>>V[i].y>>V[i].c;
	sort(V+1,V+M+1,cmp);
}

int find(int nod)
{
	while(TT[nod]!=nod)
		nod=TT[nod];
	return nod;
}

void unite(int x,int y)
{
	TT[x]=y;
}
void Solve()
{
	for(int i=1;i<=M;i++)
		if(find(V[i].x)!=find(V[i].y))
		{
			unite(find(V[i].x),find(V[i].y));
			P[++k].first=V[i].x;
			P[k].second=V[i].y;
			cost+=V[i].c;
		}
}

int main()
{
	read();
	for(int i=1;i<=M;i++)
		TT[i]=i;
	Solve();
	tu<<cost<<"\n";
	tu<<N-1<<"\n";
	for(int i=1;i<=k;i++)
		tu<<P[i].first<<" "<<P[i].second<<"\n";
	return 0;
}