//
//  main.cpp
//  arbore partial de cost minim
//
//  Created by Eusebiu Rares on 01/09/2020.
//  Copyright © 2020 Eusebiu Rares. All rights reserved.
//

#include <iostream>
#include "fstream"
#include "vector"
#include "algorithm"
#pragma GCC optimize ("O3")

template <typename T>
class InputReader {
private:
	FILE *input_file ;
	static const int SIZE = (1 << 17) ;
	int point ;
	char buffer[SIZE] ;
	__attribute__ ( (always_inline)) void advance() {
		++ point ;
		if (point == SIZE) {
			point = 0 ;
			fread (buffer, SIZE, 1, input_file) ;
		}
	}
public:
	InputReader() {}
	InputReader (const char *file_name) {
		input_file = fopen (file_name, "r") ;
		point = 0 ;
		fread (buffer, SIZE, 1, input_file) ;
	}
	__attribute__ ( (always_inline)) InputReader &operator >> (T &n) {
		for (; !isdigit (buffer[point]) ; advance()) ;
		n = 0 ;
		for (; isdigit (buffer[point]) ; advance()) {
			n = n * ( (1 << 3) + (1 << 1)) + buffer[point] - '0' ;
		}
		return *this ;
	}
} ;

InputReader<int> in("apm.in") ;
std::fstream out ("apm.out", std::ios::out) ;

const int MN = 4e5 ;

struct Edge {
	int nodex, nodey ;
	int cost ;
	Edge() {
		nodex = nodey = cost = 0 ;
	}
	Edge(int x, int y, int c) {
		nodex = x ;
		nodey = y ;
		cost = c ;
	}
} ;

Edge edges[MN + 1] ;
Edge answer[MN + 1] ;

namespace DSU {
const int MV = 2e5 ;

int dsu[MV + 1] ;
int father[MV + 1] ;

int find(int x) {
	if (x == father[x]) {
		return x ;
	}
	return x = find(father[x]) ;
}

void unite(int x, int y) {
	father[y] = x ;
}
}

int main(int argc, const char * argv[]) {
	int n, m, p(0), a(0) ; in >> n >> m ;
	for (int i = 1 ; i <= n ; ++ i) {
		DSU::father[i] = i ;
	}
	for (int i = 1 ; i <= m ; ++ i) {
		int startNode, endNode, cost ; in >> startNode >> endNode >> cost ;
		edges[++ p] = (Edge(startNode, endNode, cost)) ;
	}
	std::sort(edges + 1, edges + 1 + p, [](Edge a, Edge b) {
		return a.cost < b.cost ;
	}) ;
	int sum(0) ;
	for (int i = 1 ; i <= p ; ++ i) {
		Edge edge = edges[i] ;
		int firstSet(DSU::find(edge.nodex)) ;
		int secondSet(DSU::find(edge.nodey)) ;
		if (firstSet != secondSet) { // nu adaug in set muchia
			DSU::unite(firstSet, secondSet) ;
			sum += edge.cost ;
			answer[++ a] = (edge) ;
		}
	}
	out << sum << '\n' ;
	out << a << '\n' ;
	for (int i = 1 ; i <= a ; ++ i) {
		out << answer[i].nodex << ' ' << answer[i].nodey << '\n' ;
	}
}