//
//  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")

std::fstream in ("apm.in", std::ios::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) {
		this -> nodex = x ;
		this -> nodey = y ;
		this -> cost = c ;
	}
	bool operator < (const Edge &aux) const {
		return cost < aux.cost ;
	}
} ;

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

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) {
		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) ;
	int sum(0) ;
	for (int i = 1 ; i <= p ; ++ i) {
		Edge edge = edges[i] ;
		int firstSet(find(edge.nodex)) ;
		int secondSet(find(edge.nodey)) ;
		if (firstSet != secondSet) { // nu adaug in set muchia
			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' ;
	}
}