#include <stdlib.h>
#include <stdio.h>
#include <fstream>
#include <iostream>

using namespace std;

struct Muchie
{
	int prim, secund, pondere;
};
struct Graf
{
	int V, E;
	struct Muchie* m;
};

 Graf* alocare(int V, int E)
{
	struct Graf* G = new Graf;
	G->V = V;
	G->E = E;
	G->m = new Muchie[E];


	return G;
}

struct Multime
{
	int tata;
	int h;
};

int FindSet(struct Multime submultimi[], int i)
{
    cout<<i;
	if (submultimi[i].tata != i)
		submultimi[i].tata = FindSet(submultimi, submultimi[i].tata);

	return submultimi[i].tata;
}

void Union(struct Multime submultimi[], int x, int y)
{
	int xrad = FindSet(submultimi, x);
	int yrad = FindSet(submultimi, y);

	if (submultimi[xrad].h < submultimi[yrad].h)
		submultimi[xrad].tata = yrad;
	else if (submultimi[xrad].h > submultimi[yrad].h)
		submultimi[yrad].tata = xrad;

	else
	{
		submultimi[yrad].tata = xrad;
		submultimi[xrad].h++;
	}
}

// Compare two edges according to their weights.
// Used in qsort() for sorting an array of edges
int myComp(const void* a, const void* b)
{
	struct Muchie* a1 = (struct Muchie*)a;
	struct Muchie* b1 = (struct Muchie*)b;
	return a1->pondere > b1->pondere;
}




void apm(struct Graf* G)
{
	int V = G->V;

	struct Muchie *A = (struct Muchie*) new char[V * sizeof(struct Muchie)];
	int e = 0;
	int s = 0;
	qsort(G->m, G->E, sizeof(G->m[0]), myComp);

	struct Multime *submultimi = (struct Multime*)new char[V * sizeof(struct Multime)];

	for (int v = 0; v < V; ++v)
	{
		submultimi[v].tata = v;
		submultimi[v].h = 0;
	}
    int i = 0;
	while (e < V - 1)
	{
		struct Muchie drum = G->m[i++];


		int x = FindSet(submultimi, drum.prim);
		int y = FindSet(submultimi, drum.secund);

		if (x != y)
		{
			A[e] = drum;
			s += A[e].pondere;
			Union(submultimi, x, y);
			e++;
		}
	}

	ofstream fout("apm.out");
	fout << s << endl << e << endl;
	for (int i = 0; i<e; i++)
		fout << A[i].prim << " " << A[i].secund << endl;

}

void initializare(int &V, int &E, Graf* &G)
{
	ifstream fin("apm.in");
	fin >> V; fin >> E;

	G = alocare(V, E);
	int x,y,z;
	for (int e = 0; e<E; e++)
	{
		fin >> x >> y >> z;
		G->m[e].prim=x;
		G->m[e].secund=y;
		G->m[e].pondere=z;
	}
	fin.close();
}


int main()
{
	int V, E;
	struct Graf* G;

	initializare(V, E, G);
	apm(G);


	return 0;
}