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

typedef struct
{
	int root,rank;
} set;

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;
}

void setFind(const int& v, vector<set>& parent)
{
	if(parent[v].root!=v)	setFind(parent[v].root,parent);
	parent[v].root=parent[parent[v].root].root;
}

void Union(const int& v1, const int& v2, vector<set>& parent)
{
	if(parent[parent[v1].root].rank>parent[parent[v2].root].rank) parent[v2].root=parent[v1].root;
	else
	{
		parent[v1].root=parent[v2].root;
		if(parent[parent[v1].root].rank==parent[parent[v2].root].rank) parent[parent[v2].root].rank++;
	}
}

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<set> parent;
	fin>>N>>M;
	graph.resize(M);
	parent.resize(N);
	for(i=0;i<M;i++) fin>>graph[i];
	for(i=0;i<N;i++) {parent[i].root=i; parent[i].rank=0;}
	fin.close();
	std::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<<". ";
		setFind(graph[i].v1,parent);
		setFind(graph[i].v2,parent);
		if(parent[graph[i].v1].root!=parent[graph[i].v2].root)
		{
			//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;
}