#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <cstdio>


using namespace std;

class ComparatorMuchie;

class muchie
{
	friend ostream & operator << (ostream &, const muchie &);
	friend ComparatorMuchie;

public:
	int start, end;
	int cost;
	
public:
	muchie(int start, int end, int cost)
	: start(start), end(end), cost(cost)
	{}
	
	int either();
	int other(int);
	int getCost() { return cost; }
	
	void incr() { start++; end++; }
	void decr() { start--; end--; }
};

int muchie::either()
{
	return start;
}

int muchie::other(int vf)
{
	if (vf == start)
		return end;
	return vf;
}

ostream & operator << (ostream & out, const muchie & m)
{
	out << m.end << " " << m.start << endl;
	return out;
}

class ComparatorMuchie
{
public:
	bool operator ()(const muchie & m1, const muchie & m2)
	{
		return m1.cost > m2.cost;
	}
};

typedef priority_queue<muchie, vector<muchie>, ComparatorMuchie> MinHeapMuchie;

class QuickFind
{
	int *id;
	int N;
public:
	QuickFind(int size);
	~QuickFind();
	bool conn(int u, int v);
	void uni(int u, int v);
};

QuickFind::QuickFind(int size)
{
	N = size;
	id = new int[size];
	for(int i = 0; i < size; i++)
		id[i] = i;
}

QuickFind::~QuickFind()
{
	delete[] id;
}

bool QuickFind::conn(int u, int v)
{
	return id[u] == id[v];
}

void QuickFind::uni(int u, int v)
{
	int idu = id[u];
	
	for(int i = 0; i < N; i++)
		if (id[i] == idu)
			id[i] = id[v];
}

class UF
{
	int *id;
	int *sz;
	int size;
	int comp;
	
	int find_id(int v);
	
public:
	UF(int size);
	~UF();
	bool connected(int u, int v);
	void unify(int u, int v);
	int components() const { return comp; }
};

UF::UF(int size)
{
	this->size = size;
	comp = 0;
	id = new int[size];
	sz = new int[size];
	
	for(int i = 0; i < size; i++)
	{
		id[i] = i;
		sz[i] = 1;
	}
	
	comp = size;
}

UF::~UF()
{
	delete[] id;
	delete[] sz;
}

int UF::find_id(int v)
{
	// valideaza v
	int root = v;
	while(root != id[root])
		root = id[root];
	while(v != root)
	{
		int new_root = id[v];
		id[v] = root;
		v = new_root;
	}
	
	return root;
}

bool UF::connected(int u, int v)
{
	return find_id(u) == find_id(v);
}

void UF::unify(int u, int v)
{
	int root_u = find_id(u);
	int root_v = find_id(v);
	
	if (sz[root_u] < sz[root_v])
	{
		id[root_u] = root_v;
		sz[root_v] += sz[root_u];
	}
	else
	{
		id[root_v] = root_u;
		sz[root_u] += sz[root_v];
	}
	
	comp--;
}

int main(int argc, char **argv)
{
	
	
	// Kruskal //
	
	ifstream in("apm.in");
	MinHeapMuchie q;
	
	unsigned n,m;
	in >> n;
	in >> m;
	
	for(unsigned i = 0; i < m; i++)
	{
		int origine, extremitate, cost;
		in >> origine >> extremitate >> cost;
		muchie curent(origine, extremitate, cost);
		curent.decr();
		q.push(curent);
	}
	
	UF uf(n);
	
	int MSTcost = 0;
	

	queue<muchie> MST;
	
	while(!q.empty() && MST.size() < m)
	{
		muchie edge = q.top();
		q.pop();
		
		int v = edge.either(), w = edge.other(v);
		
		if (!uf.connected(v, w))
		{
			uf.unify(v, w);
			
			
			MST.push(edge);
			
			MSTcost += edge.getCost();
		}
	}
	
	// write data on output file and the exit
	
	ofstream out_file("apm.out");
	
	out_file << MSTcost << endl;
	out_file << MST.size() << endl;
	
	while(!MST.empty())
	{
		muchie vf = MST.front();
		vf.incr();
		MST.pop();
		out_file << vf;
	}
	
	out_file.close();
	
	
	return 0;
}