#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;

struct nod{
	int urm;
	int cost;
};
struct nodh{
	int urm;
	int cost;
	int dela;
};
#define MAXN 200003
#define MAXM 400003
bool comp(nodh a, nodh b) {
	return (a.cost>b.cost);
}


ifstream fin("apm.in");
ofstream fout("apm.out");

vector<nod> graf[MAXN];
vector<nodh> heap;
vector<nod> res;
bitset<MAXN> viz;
int i,j,n,m,a,b,c,vizitate,cost;
nod aux2;
nodh aux,aux3;

int main() {
	fin>>n>>m;
	for(i=1;i<=m;i++) {
		fin>>a>>b>>c;
		aux2.cost=c;
		aux2.urm=b;
		graf[a].push_back(aux2);
		aux.urm=a;
		graf[b].push_back(aux2);		
	}	
	aux.urm=1;
	aux.cost=0;
	heap.push_back(aux);
	while (!heap.empty()) {		
		aux=heap[0];	
		pop_heap(heap.begin(),heap.end(),comp);
		heap.pop_back();
		if (!viz[aux.urm]) {		
			cost+=aux.cost;
			aux2.urm=aux.dela;
			aux2.cost=aux.urm;
			res.push_back(aux2);
			viz[aux.urm]=1;
			vizitate++;
			if (n==vizitate) {break;}
			for(i=0;i<graf[aux.urm].size();i++) {
				if (!viz[graf[aux.urm][i].urm]) {
					aux3.dela=aux.urm;
					aux3.urm=graf[aux.urm][i].urm;
					aux3.cost=graf[aux.urm][i].cost;
					heap.push_back(aux3);
					push_heap(heap.begin(),heap.end(),comp);
				}
			}
		}
	}	
	fout<<cost<<"\n";
	fout<<res.size()-1<<"\n";
	for(i=1;i<res.size();i++) {
		fout<<res[i].cost<<" "<<res[i].urm<<"\n";
	}
	fout.close();
	return 0;
}