#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#define FIN "apm.in"
#define FOUT "apm.out"
using namespace std;

struct Edge {
	int u, v, cost;
};

class UnionFind {

public:
	UnionFind(int n) {

		parent.resize(n, 0);
		rank.resize(n, 0);

		for(int i = 0; i < n; i++) parent[i] = i;
	}

	int find(int u) { // caută rădăcina unde se află u

		if(u != parent[u]) {
			parent[u] = find( parent[u] );
		}	
		return parent[u];
	} 
	
	void Union(int u, int v) {

		int rootX = find(u);
		int rootY = find(v);

		if(rootX != rootY) {
			if( rank[rootX] < rank[rootY] ) {
			
				parent[rootX] = rootY;
			
			} else if( rank[rootX] > rank[rootY] ){
			
				parent[rootY] = rootX;
			
			} else {
			
				parent[rootY] = rootX;
				rank[rootX]++;
			
			}
		}
	}
// Funcția Union() o folosim pentru a unifica două noduri din doi arbori diferiți		

private:

	vector<int> parent;
	vector<int> rank;
};

bool compareEdge(const Edge &a, const Edge &b) {

	return a.cost < b.cost;
}

int main()
{
	ifstream inFile(FIN);
	ofstream outFile(FOUT);

	int n, m, total_cost = 0;

	inFile >> n >> m;	
	
	vector<Edge> edges(m); //declarăm un vector de muchii asociate unui cost
	
	for(int i = 0; i < m; i++) inFile >> edges[i].u >> edges[i].v >> edges[i].cost;	
/*
	for(vector<Edge>::iterator it = edges.begin(); it != edges.end(); it++) 
		cout<<"Edge ["<< (*it).u << (*it).v <<"]"<<"-> cost="<<(*it).cost<<"\n";
	
	 
	sort(edges.begin(), edges.end(), compareEdge);
	cout<<"\n-------------------\n";

	for(vector<Edge>::iterator it = edges.begin(); it != edges.end(); it++) 
		cout<<"Edge ["<< (*it).u << (*it).v <<"]"<<"-> cost="<<(*it).cost<<"\n";
	*/	
	UnionFind uf( n + 1 );

	vector<Edge> mst; // Minimum Spanning Tree

	for(const Edge &e: edges) {

		if( uf.find(e.u) != uf.find(e.v) ) { //trebuie s[] fie in arbori diferiti, UNION		
	
			uf.Union(e.u, e.v);
			mst.push_back(e);
			total_cost = total_cost + e.cost;
		}
	}

	outFile << total_cost << " " << mst.size() << "\n";

	for(const Edge& ed: mst ) 
		outFile << ed.u << " " << ed.v<<"\n"; 

	return 0;
}