#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int nmax = 400010;
vector<vector<int>> mat(nmax),mat1(nmax);
vector<pair<int,int>> ans;
vector<int> visited(nmax,0);
vector<pair<int,pair<int,int>>> edges;
int n,m,ans_suma;

void dfs(int nod){
	visited[nod] = 1;
	for(auto nod_aux : mat1[nod]){
		if(!visited[nod_aux]){
			dfs(nod_aux);
		}
	}
}
void read_input(){
	fin >> n >> m;
	int nod_1,nod_2,cost;
	for(int i = 1; i <=m; i++){
		fin >> nod_1 >> nod_2 >> cost;
		mat[nod_1].push_back(nod_2);
		mat[nod_2].push_back(nod_1);
		edges.push_back(make_pair(cost,make_pair(nod_1,nod_2)));
	}
};
void solve(){
	sort(edges.begin(),edges.end());
	int numar = n-1;
	for(int i = 0; i <m; i++){
		int cost_aux = edges[i].first;
		int nod1_aux = edges[i].second.first;
		int nod2_aux = edges[i].second.second;
		fill(visited.begin(),visited.end(),0);
		dfs(nod1_aux);
		if(!visited[nod2_aux]){
			numar--;
			mat1[nod1_aux].push_back(nod2_aux);
			mat1[nod2_aux].push_back(nod1_aux);
			ans.push_back(make_pair(nod1_aux,nod2_aux));
			ans_suma += cost_aux;
			
		};
		if(!numar){break;}
	};
	fout << ans_suma << '\n' << n-1 << '\n';
	for(auto x : ans){
		fout << x.second << " " << x.first << '\n';
	}
}
int main(){
	read_input();
	solve();
	return 0;
}