using namespace std;
#include<fstream>
#include<algorithm>
ifstream eu("apm.in");
ofstream tu("apm.out");
#define Nmax 400005
pair <int,int> P[Nmax];
int N,M,cost,TT[Nmax],k,RG[Nmax];
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)
{
	if(RG[x]<RG[y])
		TT[x]=y;
	if(RG[y]<RG[x])
		TT[y]=x;
	if(RG[x]==RG[y])
		TT[x]=y,RG[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,RG[i]=1;
	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;
}