#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct
{
	int v1,v2,cost;
} wEdge;

istream& operator >>(istream& i, wEdge& e)
{
	i>>e.v1>>e.v2>>e.cost;
	e.v1--;
	e.v2--;
	return i;
}

ostream& operator <<(ostream& o, wEdge& e)
{
	o<<e.v1+1<<' '<<e.v2+1;
	return o;
}

bool operator <(const wEdge& e1, const wEdge& e2)
{
	if(e1.cost<e2.cost) return 1;
	return 0;
}

bool operator ==(const wEdge& e1, const wEdge& e2)
{
	if(e1.cost==e2.cost) return 1;
	return 0;
}

int vertexRank(const int& v, const vector<int>& parent)
{
	int rank=0;
	for(unsigned int i=0;i<parent.size();i++)
	{
		if(parent[i]==v) rank++;
	}
	return rank;
}

void Union(const int& v1, const int& v2, vector<int>& parent)
{
	if(vertexRank(v1,parent)>vertexRank(v2,parent))
	{
		for(unsigned int i=0;i<parent.size();i++)
		{
			if(parent[i]==parent[v2] && i!=v2) parent[i]=parent[v1];
		}
		parent[v2]=parent[v1];
	}
	else
	{
		for(unsigned int i=0;i<parent.size();i++)
		{
			if(parent[i]==parent[v1] && i!=v1) parent[i]=parent[v2];
		}
		parent[v1]=parent[v2];
	}
}

bool compWEdges(const wEdge& e1, const wEdge& e2) {return e1<e2;}

int main()
{
	ifstream fin("apm.in");
	int N,M,i,costTotal=0;
	wEdge aux;
	vector<wEdge> graph;
	vector<wEdge> kruskal;
	vector<int> parent;
	fin>>N>>M;
	graph.resize(M);
	parent.resize(M,0);
	for(i=0;i<M;i++) fin>>graph[i];
	for(i=0;i<N;i++) parent[i]=i;
	fin.close();
	sort(graph.begin(),graph.end(),compWEdges);
	for(i=0;i<M;i++)
	{
		//cout<<"Checking the edge "<<graph[i].v1+1<<'-'<<graph[i].v2+1<<" of cost "<<graph[i].cost<<". ";
		if(parent[graph[i].v1]!=parent[graph[i].v2])
		{
			//cout<<"Parent of "<<graph[i].v1+1<<" is "<<parent[graph[i].v1]<<" and parent of "<<graph[i].v2<<" is "<<parent[graph[i].v2]<<".\n";
			kruskal.push_back(graph[i]);
			Union(graph[i].v1,graph[i].v2,parent);
			costTotal+=graph[i].cost;
		}
	}
	ofstream fout("apm.out");
	fout<<costTotal<<'\n'<<kruskal.size()<<'\n';
	for(i=0;i<kruskal.size();i++) fout<<kruskal[i]<<'\n';
	fout.close();
	return 0;
}