#include <fstream>
#include <vector>
#include<algorithm>

using namespace std;

struct vertex
{
	int a,b,c;
};

void read();
void solve();	
void sort(struct vertex G[],int n);
void initializeSets(int n);
vector<struct vertex> minimumSpanningTree(struct vertex G[], int m);
int findSet(int node);
void link(int a, int b);
void print(vector<struct vertex> g);
inline bool cmp(struct vertex v1,struct vertex v2)
{
	return v1.c < v2.c;
}

int N,M,SET[400005];
struct vertex G[400005];

int main()
{
	read();
	solve();
	return 0;
}

void read()
{
	ifstream fin("apm.in");
	fin>>N>>M;
	for(int i=0;i<M;i++)
	{
		fin>>G[i].a>>G[i].b>>G[i].c;
	}
}

void solve()
{
	sort(G,M);
	initializeSets(N);
	print(minimumSpanningTree(G,M));
}

void sort(struct vertex G[], int n)
{
	sort(G, G + n, cmp);
}

void initializeSets(int n)
{
	for(int i=1;i<=n;i++)
	{
		SET[i] = i;
	}
}

vector<struct vertex> minimumSpanningTree(struct vertex G[], int m)
{
	int nr = 2, i=1, sa, sb;
	vector<struct vertex> MST;
	for(int i=0;i<m;i++)
	{
		if((sa = findSet(G[i].a)) != (sb = (findSet(G[i].b))))
		{
			MST.push_back(G[i]);
			SET[sa] = sb;
			//link(G[i].a, G[i].b);
		}
	}
	return MST;
}

int findSet(int node)
{
	if(SET[node] != node)
	{
		SET[node] = findSet(SET[node]);
	}
	return SET[node];
}

void link(int a, int b)
{
	SET[findSet(a)] = findSet(b);
}

void print(vector<struct vertex> g)
{
	ofstream fout("apm.out");
	int sum = 0;
	for(unsigned int i=0;i<g.size();i++)
	{
		sum+=g[i].c;
	}
	fout<<sum<<'\n';
	fout<<g.size()<<'\n';
	for(unsigned int i=0;i<g.size();i++)
	{
		fout<<g[i].a<<' '<<g[i].b<<'\n';
	}
}