#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <chrono>
using namespace std;
using namespace chrono;

struct edge
{
	int i;
	int j;
	int weight;
};
int findMin(vector<edge> graph)
{
	int indexMin = 0;
	for (int i = 0; i < graph.size(); i++)
	{
		if (graph[i].weight < graph[indexMin].weight)
		{
			indexMin = i;
		}
	}
	return indexMin;
}
int main()
{
	int size = 0;
	cout << "Please, enter size: ";
	cin >> size;
	if (!cin)
		exit(1);
	vector<edge> graph;
	vector<edge> tree;
	for (int i = 0; i < size; i++)
	{
		edge buffer;
		cout << "Please, enter edge(i j weight): ";
		cin >> buffer.i >> buffer.j >> buffer.weight;
		graph.push_back(buffer);
	}
	if (!cin)
		exit(1);
	high_resolution_clock::time_point cl1 = high_resolution_clock::now();
	while (graph[findMin(graph)].weight != INT_MAX)
	{
		int start = 0;
		do
		{
			int index = findMin(graph);
			bool i = 0, j = 0;
			for (auto x : tree)
			{
				if (x.j == graph[index].i || x.i == graph[index].i)
				{
					i = true;
				}
				if (x.j == graph[index].j || x.i == graph[index].j)
				{
					j = true;
				}
			}
			if (i && j)
			{
				graph[index].weight = INT_MAX;
				break;
			}
			tree.push_back(graph[index]);
			graph[index].weight = INT_MAX;
			break;
		} while (true);
	}
	high_resolution_clock::time_point cl2 = high_resolution_clock::now();
	cout << endl;
	for (auto x : tree)
	{
		cout << x.i << ' ' << x.j << ' ' << x.weight << endl;
	}
	int weight = 0;
	for (auto x : tree)
	{
		weight += x.weight;
	}
	cout << "Weight: " << weight << endl;
	std::cout << "Time: " << (duration_cast<duration<double>>(cl2 - cl1)).count() << " sec." << endl;
	return 0;
}