#include <stdio.h>
int a[10][10], done[10], path[10], cost = 0, idx = 0;
int least(int c) {
		int i, nc = -1, min = 999;
		for (i = 0; i < 4; i++)
				if (!done[i] && a[c][i] && a[c][i] < min) {
						min = a[c][i];
						nc = i;
				}
		if (nc != -1) cost += min;
		return nc;
}
void tsp(int city) {
		int next;
		done[city] = 1;
		path[idx++] = city;
		next = least(city);
		if (next == -1) {
				cost += a[city][0];
				path[idx++] = 0;
				return;
		}
		tsp(next);
}
void main() {
		int i, j;
		int temp[4][4] = {
				{0, 4, 1, 5},
				{4, 0, 2, 6},
				{1, 2, 0, 3},
				{5, 6, 3, 0}
		};
		for (i = 0; i < 4; i++)
				for (j = 0; j < 4; j++)
						a[i][j] = temp[i][j];
		for (i = 0; i < 4; i++)
				done[i] = 0;
		tsp(0);
		printf("PATH: ");
		for (i = 0; i < idx; i++)
				printf("%d ", path[i] + 1);
		printf("\nTOTAL COST = %d\n", cost);
}