#include<fstream>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAX 200000
class muchie
{
public:
	int nod1,nod2,cost;
	bool operator<(muchie e) const
	{
		if(cost<e.cost) return 1;
		return 0;
	}
};
ifstream in("apm.in");
ofstream out("apm.out");
int parent[MAX],h[MAX],n,m;
vector<pair<int,int>> finalEdges;
void MakeSet(int u)
{
	parent[u]=0;
	h[u]=1;
}
int FindSet(int u)
{
	if(parent[u]==0)
		return u;
	else 
	{
			parent[u]=FindSet(parent[u]);
			return parent[u];
	}
}
void Union(int u,int v)
{
	int x=FindSet(u);
	int y=FindSet(v);
	if(h[x]<h[y]) parent[x]=y;
	else 
	{
		parent[y]=x;
		if(h[x]==h[x]) 
			h[x]++;
	}
}
void Kruskal(vector<muchie> edge)
{
	for (int i=1;i<=m;i++)
		MakeSet(i);
	std::sort(edge.begin(),edge.end());
	//edge_sort();
	int i=0,cost_minim=0,edgeCnt=0;
	while(edgeCnt<n && i<m )
	{
		int u=edge[i].nod1;
		int v=edge[i].nod2;
		if(FindSet(u)!=FindSet(v))
		{
			//out<<u<<" "<<v<<" "<<endl;
			finalEdges.push_back(make_pair(u,v));
			edgeCnt++;
			cost_minim+=edge[i].cost;
			Union(u,v);
		}
		i++;
	}
	out<<cost_minim<<endl<<n-1<<endl;
}
int main()
{ 
	in>>n>>m;
	vector<muchie> edge(m);
	for(int i=0;i<m;i++)
		in>>edge[i].nod1>>edge[i].nod2>>edge[i].cost;
	in.close();
	Kruskal(edge);
	for(int i=0;i<finalEdges.size();i++)
		out<<finalEdges[i].first<<" "<<finalEdges[i].second<<endl;
	out.close();
	return 0;
}