Algo10C

#include <fstream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

int FindRoot(vector<int> &roots, int v)
{
	if (v != roots[v])
		roots[v] = FindRoot(roots, roots[v]);
	return roots[v];
}

void Kruskal( vector<int> &roots, vector<int> &rootssize, long long &answer, int v1, int v2, int weight)
{
	if (v1 != v2)
	{
		answer += weight;
		if (rootssize[v1] < rootssize[v2])
			swap(v1, v2);
		roots[v2] = v1;
		rootssize[v1] += rootssize[v2];
	}
}

int main()
{
	ifstream fcin("spantree3.in");
	ofstream fcout("spantree3.out");

	int n, m;
	fcin >> n >> m;

	vector<tuple<int, int, int>> edges(m);
	vector<int> roots(n);
	vector<int> rootssize(n, 1);

	for (int i = 0; i < n; i++)
		roots[i] = i;

	for (int i = 0; i < m; i++)
	{
		int in, out, way;
		fcin >> out >> in >> way;
		edges[i] = {way, out - 1, in - 1};
	}

	sort(edges.begin(), edges.end());

	long long answer = 0;
	for (int i = 0; i < edges.size(); i++)
	{
		int weight = get<0>(edges[i]), v1 = FindRoot(roots, get<1>(edges[i])), v2 = FindRoot(roots, get<2>(edges[i]));
		Kruskal(roots, rootssize, answer, v1, v2, weight);
	}

	fcout << answer;

	return 0;
}