#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/iteration_macros.hpp>
#define _SCL_SECURE_NO_WARNINGS
using namespace std;

int main()
{
	setlocale(LC_ALL, "Russian");
	ifstream in("input.txt");
	ofstream out("output.txt");
	out << "graph G {" << endl;
	int m;//кол-во ребер
	int n;//кол-во вершин
	in >> n;
	in >> m;
	int x, y, z;//считываем дуги и вес
	vector < pair < int, pair<int, int> > > g(m); // вес - вершина 1 - вершина 2

	vector < pair < int, pair<int, int> > > res;//массив для хранения дуг остовного дерева и их весов


	for (int i = 0; i < m; i++)
	{
		in >> x >> y >> z;
		g[i].first = z;
		g[i].second.first = x;
		g[i].second.second = y;
	}
	int tree_weight = 0;

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

	vector<int> tree_id(n);

	for (int i = 1; i < n; i++) {
		tree_id.push_back(NULL);
	}
	for (int i = 0; i < m; i++) {
		res.push_back(make_pair(NULL, make_pair(NULL, NULL)));
	}
	for (int i = 1; i < n; ++i)
		tree_id[i] = i;
	for (int i = 0; i < m; ++i)
	{
		int a = g[i].second.first, b = g[i].second.second, l = g[i].first;
		if (tree_id[a] != tree_id[b])
		{
			tree_weight += l;
			res[i].first = l;
			res[i].second=(make_pair(a, b));
			int old_id = tree_id[b], new_id = tree_id[a];
			for (int j = 1; j < n+1; ++j)
				if (tree_id[j] == old_id)
					tree_id[j] = new_id;
		}
	}
	cout << "Ребра минимального остовного дерева: " << endl;
	for (int i = 0; i < res.size(); i++) {

		if (res[i].second.first != NULL) {  //[label=1, weight=1];
			out << res[i].second.first << " -- " << res[i].second.second << " " << "[label=" << res[i].first << "];" << endl;
			cout << res[i].second.first << " , " << res[i].second.second << " " << res[i].first << endl;
		}

	}
	cout << endl;
	for (int i = 0; i < tree_id.size(); i++) {
		if(tree_id[i])
		cout << tree_id[i];
	}
	cout << endl;
	in.close();
	out << "}";
	out.close();
	cout << "Вес минимального остовного дерева: "<< tree_weight <<endl;
	system("dot output.txt -Tpng -og.png");
}