/*
 * main.cpp
 *
 *  Created on: Mar 13, 2009
 *      Author: alex
 */
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#define nMax 100000
#define inf 0x3f3f3f3f

typedef struct{
	int to, c;
} muchie;

vector<muchie> G[nMax];
int d[nMax], dist[nMax], P[nMax], padre[nMax], v[nMax], rez[nMax], n, m;

muchie make_edge(int x, int y){
	muchie rez;
	rez.to = x, rez.c = y;
	return rez;
}

int comp(int a, int b){
	return dist[a]<dist[b];
}

void heap_push(int x){
	int size = d[0]+1;
	d[size] = x;
	P[x] = size;
	int it = size, padre = it >> 1;
	while ( padre > 0 && comp(d[it], d[padre]) ){

		swap(P[d[it]], P[d[padre]]);
		swap(d[it], d[padre]);
		it = padre;
		padre = it >> 1;
	}

	d[0] = size;
}

int heap_pop(){
	int rez = d[1], size = d[0];
	d[1] = d[size],	size -= 1, P[d[1]] = 1;
	int it = 1;
	int son = comp(d[it*2],d[it*2+1])?it*2:it*2+1;
	while (son <= size && !comp(d[it], d[son]) ){
		swap(P[d[it]], P[d[son]]);
		swap(d[it], d[son]);
		it = son;
		son = comp(d[it*2],d[it*2+1])?it*2:it*2+1;
	}

	d[0] = size;
	return rez;
}

void heap_update(int x){
	int it = P[x];
	int padre = it >> 1;
	while (padre > 0 && comp(d[it], d[padre])){
		swap(P[d[it]], P[d[padre]]);
		swap(d[it], d[padre]);
		it = padre;
		padre = it >> 1;
	}

}

void citire(){
	ifstream fin("apm.in");
	fin >> n >> m;
	for (int i=0; i<m;i++){
		int a, b, c;
		fin >> a >> b >> c;
		G[a].push_back(make_edge(b,c));
		G[b].push_back(make_edge(a,c));
		dist[i+2] = inf, P[i+2] = 0;
	}
	fin.close();
}

void apm(){
	dist[1] = 0;
	heap_push(1);
	while (d[0]){
		int last = heap_pop();
		v[last] = 1;
		for (vector<muchie>::iterator it = G[last].begin(); it != G[last].end(); it++){
			int x = (*it).to;
			// nu a fost selectat pentru solutie
			if (!v[x]){
				// daca se poate relaxa distanta
				if ((*it).c < dist[x])
					dist[x] = (*it).c, padre[x] = last;

				// daca nu e candidat
				if (P[x] == 0)
					heap_push(x), padre[x] = last;
				else
					heap_update(x);
			}
		}
	}
}

void scriere(){
	ofstream fout("apm.out");
	int rezf = 0;
	for (int i=2;i<=n;i++)
		//cout << dist[i] << " ";
		rezf += dist[i];
	//cout << "\n";
	fout << rezf << "\n" << n-1 << "\n";
	for (int i=2;i<=n;i++)
		fout << i << " " << padre[i] << "\n";
	fout.close();
}

int main(){
	citire();
	apm();
	scriere();
	return 0;
}