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

std::fstream in ("apm.in", std::ios::in) ;
std::fstream out ("apm.out", std::ios::out) ;

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 ;;
	}
} ;

namespace DSU {
const int MV = 2e5 ;

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

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

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

int main(int argc, const char * argv[]) {
	int n, m ; in >> n >> m ;
	for (int i = 1 ; i <= n ; ++ i) {
		DSU::father[i] = i ;
		DSU::rg[i] = 1 ;
	}
	std::vector<Edge> edges ;
	for (int i = 1 ; i <= m ; ++ i) {
		int startNode, endNode, cost ; in >> startNode >> endNode >> cost ;
		edges.push_back(Edge(startNode, endNode, cost)) ;
	}
	std::sort(begin(edges), end(edges)) ;
	std::vector<Edge> answer ;
	int sum(0) ;
	for (int i = 0 ; i < edges.size() ; ++ 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.push_back(edge) ;
		}
	}
	out << sum << '\n' ;
	out << answer.size() << '\n' ;
	for (auto it : answer) {
		out << it.nodex << ' ' << it.nodey << '\n' ;
	}
}