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

using namespace std ;

ifstream cin ("apm.in") ;
ofstream cout ("apm.out") ;

class DisjointDataSet
{
	public:
	DisjointDataSet(int n){
		tata.resize (n + 1) ;
		rang.resize (n + 1) ;
		fill(rang.begin(), rang.end(), 1) ;
		for (int i = 1; i <= n; ++ i) {
			tata [i] = i ;
		}
 	}
 	bool IsSame (int x, int y) {
 		return (stramos(x) == stramos (y)) ;
 	}
 	void Unite (int x, int y) {
 		unite (x, y) ;
 	}
	private :
	int stramos (int nod) {
		int R = nod ; 
		while (R != tata [R]) {
			R = tata [R] ; 
		}
		while (nod != tata [nod]) {
			int aux = tata [nod] ; 
			tata [nod] = R ;
			nod = aux ;
		}
		return R ;
	}
	void unite (int x, int y) {
		x = stramos (x) ; 
		y = stramos (y) ;

		if (x == y) {
			return ; 
		}
		if (rang [x] < rang [y]) {
			swap(x, y) ;
		}
		rang [x] += rang [y] ;
		tata [y] = tata [x] ;
	}
	vector <int> tata ;
	vector <int> rang ;

	
};

int main(int argc, char const *argv[])
{
	int n, m ;
	cin >> n >> m ;
	vector <pair<int, pair<int, int>>> Edges ;
	while (m --){
		int x, y, cost ;
		cin >> x >> y >> cost ;
		Edges.push_back(make_pair(cost, make_pair(x, y))) ;
	}
	sort (Edges.begin(), Edges.end()) ;
	DisjointDataSet *D = new DisjointDataSet (n) ; 
	vector <pair<int, int>> Sol ;
	int S = 0 ; 
	for (auto x : Edges) {
		if (!D -> IsSame (x.second.first, x.second.second)) {
			Sol.push_back (x.second) ; 
			S += x.first ;
			D -> Unite (x.second.first, x.second.second) ;
		}
	}
	cout << S << '\n' ;
	cout << Sol.size() << '\n' ;
	for (auto x : Sol) {
		cout << x.first << ' ' << x.second << '\n' ;
	}
	return 0;
}