#include <stdlib.h>
#include <stdio.h>

int **graph;
struct DOT{
	int begin;
	int end;
	int weight;
};
int dots; // кол-во вершин
int edges; // кол-во ребер
int minsaksess = INT_MAX; // минимальный самый
int *minsakksess; // путь сохраненный
DOT* dotes;

void DoTravel(int nextstep, int min, int *path, bool *flags, int it);

int main(){
	FILE *input = fopen("graph.txt", "r+");
	if (input == NULL){
		printf("CANNOT OPEN THIS \n");
	}
	else{
		fscanf(input, "%d%d", &dots, &edges);
		dotes = (DOT *)malloc(edges * 2 * sizeof(DOT)); // массив структур
		minsakksess = (int *)malloc(dots *sizeof(int));
		graph = (int **)malloc(dots*sizeof(int));
		for (int i = 0; i < dots; i++)
			graph[i] = (int *)malloc(edges*sizeof(int));
		for (int i = 0; i < dots; i++){
			for(int j = 0; j < edges; j++){
				fscanf(input, "%d", &graph[i][j]);
			}
		}
		fclose(input);
		int step = 0;
		for (int i = 0; i < dots; i++){
			for (int j = 0; j < edges; j++){
				if (graph[i][j]>0){
					for (int o = i + 1; o < dots; o++){
						if (graph[o][j] == graph[i][j]){
							dotes[step].begin = i;
							dotes[step].end = o;
							dotes[step].weight = graph[i][j];
							step++;
							dotes[step].begin = o;
							dotes[step].end = i;
							dotes[step].weight = graph[i][j];
							step++;
						}
					}
				}
			}
		}
		printf("Edges: %d \n", step);
		for (int i = 0; i < edges * 2; i++){
			printf("Edge [%d]: \t begin: %d   end: %d   weight %d \n", i + 1, dotes[i].begin + 1, dotes[i].end + 1, dotes[i].weight);
		}
		int *path = (int *)malloc(dots*sizeof(int));
		bool *flags = (bool *)malloc(dots*sizeof(bool));
		for (int i = 0; i < dots; i++){
			path[i] = 0;
			flags[i] = false;
		}
		DoTravel(0, 0, path, flags, 0);

		//сохраняем в graphviz

		FILE *output = fopen("GRAPH.dot", "w+");
		fprintf(output, "digraph  {\n");
		for (int i = 0; i < dots; i++)
			fprintf(output, "  %d;\n", i+1);
		step = 0;
		for (int i = 0; i < dots - 1; i++){
			for (int j = 0; j < edges * 2; j++){
				if (minsakksess[i] == dotes[j].begin && minsakksess[i + 1] == dotes[j].end){
					fprintf(output, "  %d -> %d [ label = \"%d\" ]\n", minsakksess[i] + 1, minsakksess[i + 1] + 1,dotes[j].weight);
				}
			}
		}
		fprintf(output, "}");
		fclose(output);
		free(dotes);
		free(path);
		free(flags);
		free(graph);
	}
	return 0;
}

void DoTravel(int nextstep, int min, int *path, bool *flags, int it){
	int count = 0;
	path[it] = nextstep;
	flags[nextstep] = true;
	for (int i = 0; i < dots; i++){
		if (flags[i] == true)
			count++;
	}
	if (count == dots){
		if (min < minsaksess){
			minsaksess = min;
			for (int i = 0; i < dots; i++){
				minsakksess[i] = path[i];
				printf("%d -> ", path[i]+1);
			}
			printf("%d \n", min);
		}
	}
	else{
		for (int i = 0; i < edges * 2; i++){
			if (dotes[i].begin == nextstep && flags[dotes[i].end] != true){
				int *_path = (int *)malloc(dots*sizeof(int));
				bool *_flags = (bool *)malloc(dots*sizeof(bool));
				for (int i = 0; i < dots; i++){
					_path[i] = path[i];
					_flags[i] = flags[i];
				}
				DoTravel(dotes[i].end, min + dotes[i].weight, _path, _flags, it + 1);
				free(_flags);
				free(_path);
			}
		}
	}
}