#include "pch.h"
#include <iostream>
#include <string>
#include <fstream>

using namespace std;

int vertex; //đỉnh
int edge; //cạnh

int minKey(int *key, bool *arr_not_review) {
	int min = INT_MAX;
	int min_index;
	for (int i = 0; i < vertex; i++) {
		if (arr_not_review[i] == false && key[i] < min) {
			min = key[i];
			min_index = i;
		}
	}
	return min_index;
}

void WriteFile(char *outputName, int *parent1, int *parent2, int *key) {
	fstream fileoutput;
	fileoutput.open(outputName, ios_base::out);

	int sum = 0;
	for (int i = 0; i < vertex; i++) {
		sum = sum + key[i];
	}
	fileoutput << sum << endl;

	for (int i = 1; i < vertex; i++) {
		if (i == vertex - 1) {
			fileoutput << "(" << parent1[i] << ";" << parent2[i] << ")";
		}
		else {
			fileoutput << "(" << parent1[i] << ";" << parent2[i] << "), ";
		}
	}
}

void Prim(int **arrGraph, bool *arr_not_review, char *outputName) {
	int *parent1 = new int[vertex]; // array vertex head
	int *parent2 = new int[vertex]; // array vertex tail
	int *key = new int[vertex];
	for (int i = 0; i < vertex; i++) {
		key[i] = INT_MAX;
	}
	key[0] = 0;
	parent1[0] = -1;
	parent2[0] = -1;
	// prim
	for (int count = 0; count < vertex - 1; count++) {
		// find vertex have key min
		int u = minKey(key, arr_not_review);
		arr_not_review[u] = true;
		for (int i = 1; i < vertex; i++) {
			if (arrGraph[u][i] && arr_not_review[i] == false && arrGraph[u][i] < key[i]) {
				parent1[i] = u;
				parent2[i] = i;
				key[i] = arrGraph[u][i];
			}
		}
	}

	// sort result (edge)
	for (int i = 1; i <= vertex -1; i++) {
		for (int j = 1; j <= vertex - i - 1; j++) {
			if (parent1[j] > parent1[j + 1]) {
				int temp1 = parent1[j];
				parent1[j] = parent1[j + 1];
				parent1[j + 1] = temp1;

				int temp2 = parent2[j];
				parent2[j] = parent2[j + 1];
				parent2[j + 1] = temp2;
			}
			if (parent1[j] == parent1[j + 1]) {
				if (parent2[j] > parent2[j + 1]) {
					int temp1 = parent1[j];
					parent1[j] = parent1[j + 1];
					parent1[j + 1] = temp1;

					int temp2 = parent2[j];
					parent2[j] = parent2[j + 1];
					parent2[j + 1] = temp2;
				}
			}
		}
	}

	//write file
	WriteFile(outputName, parent1, parent2, key);
}

void Run(char *inputName, char *outputName) {
	//read file
	fstream fileInput;
	fileInput.open(inputName, ios_base::in);
	if (fileInput.fail()) //check exists
	{
		cout << "Failed to open this file!" << endl;
	}
	else if(fileInput.peek() == std::ifstream::traits_type::eof()) // check empty
	{
		cout << "Empty file!" << endl;
	}
	else {
		// read vertex - edge
		fileInput >> vertex; fileInput >> edge;

		if (edge == 0 || vertex == NULL || edge == NULL) {
			fstream fileoutput;
			fileoutput.open(outputName, ios_base::out);
			fileoutput << "NULL";
		}
		else {
			// declare matrix graph
			// declare row
			int **arrGraph = new int*[vertex];
			// declare col
			for (int i = 0; i < vertex; i++) {
				arrGraph[i] = new int[vertex];
			}

			// array vertex not review
			bool *arr_not_review = new bool[vertex];
			for (int i = 0; i < vertex; i++) {
				// set label for vertexs
				arr_not_review[i] = false;
				// set items of matrix = 0
				for (int j = 0; j < vertex; j++) {
					arrGraph[i][j] = 0;
				}
			}

			//read and import edge (create matrix)
			int head, tail, width;
			int checkformat = 0;
			for (int i = 0; i < edge; i++) {
				fileInput >> head >> tail >> width;
				// check format (width = 0 => fail)
				if (width == 0 || width == NULL) {
					checkformat++;
				}
				arrGraph[head][tail] = width;
				arrGraph[tail][head] = width;
			}

			if (checkformat == 0) {
				// Prim
				Prim(arrGraph, arr_not_review, outputName);
				cout << "Successfull." << endl;
			}
			else {
				cout << "Width incorrect format!" << endl;
			}
		}
	}
	fileInput.close();
}



int main(int argc, char *argv[])
{
	Run(argv[1], argv[2]);
	return 0;
}