#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);
vector<pair<int,pair<int,int>>> edges;
vector<int> parent(nmax,0),rang(nmax,0);
vector<pair<int,int>> ans;
int n,m,ans_suma;

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)));
	}
};
int find_set(int nod){
	if(parent[nod] == 0){
		return nod;
	}else{
		return parent[nod] = find_set(parent[nod]);
	}
};
void union_sets(int nod_1,int nod_2){
	nod_1 = find_set(nod_1);
	nod_2 = find_set(nod_2);
	if(nod_1 != nod_2){
		if(rang[nod_1] < rang[nod_2]){
			swap(nod_1,nod_2);
		}
		parent[nod_2] = nod_1;
		rang[nod_1]++;
	}
}
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;
		if(find_set(nod1_aux) != find_set(nod2_aux)){
			numar--;
			ans_suma += cost_aux;
			ans.push_back(make_pair(nod1_aux,nod2_aux));
			union_sets(nod1_aux,nod2_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;
}