#include <fstream>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

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

struct Muchie { int x,y,c; } u[400001];
int N,M,arc[200001],L[200001];

/* int partitionare (int s, int d)
{
//    int pivot = u[s+rand()%(d-s+1)].c;
    int pivot = u[s].c;
    int i=s,j=d;
    Muchie aux;
    while (i < j) {
          cout << i << " " << j << " " << "\n";
          while (u[i].c<pivot) i++;
          while (u[j].c>pivot) j--;
          while (u[i].c == u[j].c) { i++; j--; }
          if (i < j) { aux=u[i]; u[i] = u[j]; u[j] = aux; }
    }
    return i;
}*/
int partitionare (int s, int d)
{
    int i=s,j=d,pi=0,pj=1,aux2;
    Muchie aux;
    while (i<j) {
       if (u[i].c > u[j].c) { aux=u[i]; u[i] = u[j]; u[j] = aux; aux2=pi; pi=pj;pj=aux2; }
       i+=pi;
       j-=pj;
    }
    return i;
    
}

void quicksort (int x, int y)
{
    if (x < y) {
       cout << "quicksort(" << x << "," << y << ")" << '\n';
       int m = partitionare(x,y);
       cout << "  - returneaza " << m << '\n';
       quicksort(x, m-1);
       quicksort(m+1, y);
    }
}

int main ()
{
    srand(time(NULL));
	int i, j;
	in >> N >> M;
	for (i=1; i<=M; i++)
		in >> u[i].x >> u[i].y >> u[i].c;
	in.close();
	int k=1;
	Muchie aux;
	quicksort(1, M);
	for (i=1; i<=N; i++) L[i] = i;
	i=1;
	long long cost = 0;
	while (k < N) {
		if (L[u[i].x] != L[u[i].y]) {
			int a=L[u[i].x], b=L[u[i].y];
			arc[k] = i;
			cost += u[i].c;
			for (j=1; j<=N; j++)
				if (L[j] == b) L[j] = a;
			k++;
		}
		i++;
	}

	out << cost << '\n';
	out << N-1 << '\n';
	for (i=1; i<N; i++) out << u[arc[i]].x << ' ' << u[arc[i]].y << '\n';
	out.close();
	return 0;
}