#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

std::ifstream f("apm.in");
std::ofstream gout("apm.out");

int _OP_COUNTER = 0;
class SetForest {
public:
    std::vector<int> pi;
    std::vector<int> rank;
public:
    SetForest(int size){
        pi.resize(size);
        rank.resize(size);
    }
    
    void make_set(int item) {
        pi[item] = item;
        rank[item] = 0;
    }

    int find_set(int item) {
       if (pi[item] == item)
            return item;
        return pi[item] = find_set(pi[item]);
    }

    void union_sets(int x, int y) {
        int setX = find_set(x);
        int setY = find_set(y);
        if (rank[setX] > rank[setY]) {
            pi[setY] = setX;
        }
        else {
            pi[setX] = setY;
            if (rank[setX] == rank[setY])
                rank[setY]++;
        }
    }
};

template<typename T = int, typename HeapRelation = std::greater<T> >
class priority_queue
{
private:
	std::vector<T> values;
public:
	priority_queue() {   }
	priority_queue(std::vector<T> toCopy)
	{
		values = toCopy;
		for (int i = (values.size() - 2) / 2; i >= 0; i--)
			heapify(i);
	}

	void pop()
	{
		_OP_COUNTER++;
		values[0] = values[values.size() - 1];
		heapify(0);
		values.pop_back();
	}

	T& top()
	{
		return values[0];
	}

	void push(T item)
	{
		values.push_back(item);
		climb_item(values.size() - 1);
	}

	int size()
	{
		return values.size();
	}

	void heapify(int i)
	{
		HeapRelation heapRelation;
		while (true)
		{
			int l = i * 2 + 1;
			int r = i * 2 + 2;
			int high_index = i;

			_OP_COUNTER++;
			if (l < size() && !heapRelation(values[high_index], values[l]))
				high_index = l;

			_OP_COUNTER++;
			if (r < size() && !heapRelation(values[high_index], values[r]))
				high_index = r;

			if (high_index != i)
			{
				_OP_COUNTER += 3;
				swap(values[i], values[high_index]);
				i = high_index;
			}
			else return;
		}
	}
private:
	void climb_item(int i)
	{
		HeapRelation heapRelation;
		while (true)
		{
			if (i == 0)return;
			int p = (i - 1) / 2;
			if (p < 0)return;
			_OP_COUNTER++;
			if (heapRelation(values[p], values[i])) return;

			_OP_COUNTER += 3;
			swap(values[p], values[i]);
			i = p;
		}
	}

	static inline void swap(T& x, T& y) { T aux; aux = y; y = x; x = aux; }
};

class Graph {
public:
	class Edge {
	private:
		int vertexX;
		int vertexY;
		int cost;
	public:
		Edge() {
	
		}
		Edge(int vertexX, int vertexY, int cost) {
			this->vertexX = vertexX;
			this->vertexY = vertexY;
			this->cost = cost;
		}
		inline void tie(int& x, int& y, int& c) {
			x = vertexX;
			y = vertexY;
			c = cost;
		}

		class less{
		public:
			bool operator()(Edge e, Edge f) {
				return e.cost < f.cost;
			}
		};
	};

	std::vector<Edge> edgeList;
	int vertexCount;

	Graph() {

	}

	Graph(int vertexCount) {
		this->vertexCount = vertexCount;
	}

	inline void add_edge(Edge e) {
		edgeList.push_back(e);
	}
};

class Graphs {
public:
	static Graph getMinSpanningTree(Graph G, int *total_cost = NULL) {
		if (total_cost != NULL) *total_cost=0;
		Graph result(G.vertexCount);
		priority_queue<Graph::Edge, Graph::Edge::less> priorityEdges(G.edgeList);
		SetForest dsf(result.vertexCount);
		for (int i = 0; i < result.vertexCount; i++) {
			dsf.make_set(i);
		}
	
		while (priorityEdges.size()) {
			int x, y, c;
			Graph::Edge edge;
			edge = priorityEdges.top();
			edge.tie(x, y, c);
			priorityEdges.pop();
			if (dsf.find_set(x) != dsf.find_set(y)) {
				result.add_edge(edge);
				if (total_cost != NULL) *total_cost += c;
				dsf.union_sets(x, y);
				if (result.edgeList.size() == result.vertexCount - 1) 
					break;
			}
		}
		
		return result;
	}
};

int main()
{
	int n, m, total_cost=0;
	f >> n >> m;
	Graph g(n);

	for (; m; m--) {
		int x, y, c;
		f >> x >> y >> c;
		Graph::Edge edge(x-1, y-1, c);
		g.add_edge(edge);
	}
	
	Graph minTree = Graphs::getMinSpanningTree(g, &total_cost);

	gout << total_cost << '\n' << minTree.edgeList.size() << '\n';
	for (Graph::Edge edge : minTree.edgeList) {
		int x, y, c;
		edge.tie(x, y, c);
		gout << x+1 << ' ' << y+1 << '\n';
	}
	
   

}