#include <stdio.h>
#include <map>
#include <vector>

using namespace std;

struct TEdge
{
	int Dest, Weight;
};

struct TEdge2
{
	int Source, Dest;
};

vector <TEdge> v[200005];
multimap <int, TEdge2> x;

vector <TEdge2> sol;


FILE * fin;
FILE * fout;

int N,M;

int visited[200005];

//--------------------------------------
void citire()
{
	fin = fopen("apm.in","r");
	fout = fopen("apm.out","w");
	
	fscanf(fin,"%d %d",&N,&M);
	int a;
	
	TEdge muchie,muchie2;
	for (int i=0; i<M; i++)
	{
		fscanf(fin,"%d %d %d",&a,&muchie.Dest,&muchie.Weight);
		
		v[a].push_back(muchie);
		muchie2.Dest=a;
		muchie2.Weight=muchie.Weight;
		v[muchie.Dest].push_back(muchie2);
	}
	
	fclose(fin);
}
//--------------------------------------
void solve()
{
	int Node = 1,i,mini,s=0;
	TEdge2 a;
	
	multimap <int, TEdge2>::iterator it;	
	
	while (1==1)
	{
		visited[Node]=1;
		
		//cautam si stergem celelalte muchii
		for (i=0; i<v[Node].size(); i++)
		{
			it = x.find(v[Node][i].Weight);
			
			while ((it->first==v[Node][i].Weight)&&(it->second.Dest!=Node))
				it++;
				
			if ((it->first==v[Node][i].Weight)&&(it->second.Dest==Node))
			{
				x.erase(it);
			}
		}
		
		//Adaug muchiile
		for (i=0; i<v[Node].size(); i++)
		if (visited[v[Node][i].Dest]==0)
		{
			a.Source=Node;
			a.Dest=v[Node][i].Dest;
			x.insert(pair<int,TEdge2>(v[Node][i].Weight,a));
		}
		
		if (x.size()==0) break;
		
		it = x.begin();
		
		mini =it->first;
		s=s+mini;
		Node=it->second.Dest;
		
		sol.push_back(it->second);
	}
	
	fprintf(fout,"%d\n",s);
	fprintf(fout,"%d\n",sol.size());
	for (i=0; i<sol.size(); i++)
		fprintf(fout,"%d %d\n",sol[i].Source,sol[i].Dest);
}
//--------------------------------------
int main()
{
	citire();
	
	solve();
	
	fclose(fout);
	return 0;
}