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

//structura care retine toate datele despre o muchie
struct muchie
{
	int a, b, c;
};
//citirea
void citire(vector<muchie> &much, int &n, int &m)
{
	ifstream f("muchii.in");
	f >> n;
	int x, y, z;
	while (f >> x >> y >> z)
	{
		much.push_back(muchie());
		much.back().a = x;
		much.back().b = y;
		much.back().c = z;
		m++;
	}
	f.close();
}
//functia de comparare pentru sortarea muchiilor
int cmp(muchie i, muchie j) { return i.c < j.c; }
//functie recursiva care returneaza tatal unui nod
int find(int x, vector<pair<int, int>> &tata)
{
	if (tata[x].first == x) return x;
	else return find(tata[x].first, tata);
}
//uneste tatii a doi arbori partiali
void uni(int x, int y, vector<pair<int, int>> &tata)
{
	if (tata[x].second > tata[y].second)
		tata[y].first = x;
	else if (tata[x].second < tata[y].second)
		tata[x].first = y;
	else
	{
		tata[y].first = x;
		tata[x].second++;
	}
}
//algoritmul lui Kruskal
int APM(vector<muchie> &apm, int n, int m, vector<muchie> much)
{
	//sortam muchiile
	sort(much.begin(), much.end(), cmp);
	int s = 0, k = 0, i = 0, j;
	//vector de tati
	vector<pair<int, int>> tata(n + 1);
	//prima oara fiecare nod e initializat cu el insusi, adica
	//fiecare e radacina lui
	for (j = 1; j <= n; j++) tata[j].first = j;
	//de i ori
	while (k < n - 1)
	{
		//r1 radacina primei extremitati iar r2 rad celei de a doua
		int r1 = find(much[i].a, tata);
		int r2 = find(much[i].b, tata);
		//daca fac parte din arbori diferiti
		if (r1 != r2)
		{
			//adaugam muchia la APM
			apm.push_back(muchie());
			apm.back().a = much[i].a;
			apm.back().b = much[i].b;
			apm.back().c = much[i].c;
			//crestem suma
			s = s + much[i].c;
			//crestem nr. de muchii alese
			k++;
			//unim cei doi arbori partiali
			uni(r1, r2, tata);
		}
		//trecem la muchia urmatoare
		i++;
	}
	return s;
}

int main()
{
	vector<muchie> much;
	int n, m = 0;
	citire(much, n, m);
	vector<muchie> apm;
	int s = APM(apm, n, m, much);
	cout << "Suma APM: " << s << endl << "APM: ";
	for (auto i : apm)
		cout << i.a << "-" << i.b << "-" << i.c << " ";
	cout << endl << endl;
}