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

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


class MinPQ
{
	muchie **pq;
	int capacity;
	int N;
	
	// array helper functions
	inline void exch(int i, int j);
	inline bool greater(int i, int j);
	
	// heap helper functions
	void swim(int k);
	void sink(int k);
	
public:
	MinPQ(int size);
	~MinPQ();
	bool empty() { return N == 0; }
	void insert(muchie * key);
	muchie *min() { return pq[1]; }
	muchie *delMin();
};

MinPQ::MinPQ(int size)
{
	capacity = size+1;
	N = 0;
	pq = new muchie*[size+1];
}

MinPQ::~MinPQ()
{
	delete[] pq;
}

inline void MinPQ::exch(int i, int j)
{
	muchie *temp = pq[i];
	pq[i] = pq[j];
	pq[j] = temp;
}

inline bool MinPQ::greater(int i, int j)
{
	return pq[i]->cost > pq[j]->cost;
}

void MinPQ::swim(int k)
{
	while(k > 1 && greater(k/2, k))
	{
		exch(k/2, k);
		k = k/2;
	}
}

void MinPQ::sink(int k)
{
	while(2*k <= N)
	{
		int j = 2*k;
		if (j < N && greater(j, j+1)) j++;
		if (!greater(k, j)) break;
		exch(k ,j);
		k = j;
	}
}

void MinPQ::insert(muchie * key)
{
	pq[++N] = key;
	swim(N);
}

muchie *MinPQ::delMin()
{
	exch(1, N);
	muchie *min = pq[N--];
	sink(1);
	pq[N+1] = NULL;
	return min;
}

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

	queue<muchie *> MST;
	
	while(!q.empty() && MST.size() < m)
	{
		muchie *edge = q.delMin();
		
		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;
}