#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define MAXM 7000

/* Náhodné cislo z intervalu [0, 1) */
double randdouble() {
    return rand()/(double(RAND_MAX)+1);
}

struct Mesto {
	int x;
	int y;
};

struct Val {
	long double d;
	int i;
	bool operator<(const Val &v) const {
		return d < v.d;
	}
};

char line[1024];

long double dd[MAXM][MAXM];
vector<Val> D[MAXM];
bool navstiven[MAXM];

long double F[MAXM][MAXM];
long double B[MAXM][MAXM];

long double R = 0.5;
long double alpha = 2;
long double beta = 2;

int N = 1000;
int ITERACE = 1000;
int K = 10;

int M = 0;
Mesto mesta[MAXM];

int best = 1000000000;

vector<int> mravenci_cesta() {
	int navstiveno = 0;
	for (int i=0; i<M; i++) navstiven[i] = false;
	int start = rand()%M;
	navstiven[start] = true; navstiveno++;
	int akt = start;
	vector<int> res; res.push_back(akt);

	while (navstiveno<M) {
		vector<int> v;
		for (int a=0; a<M-1; a++) {
			int i = D[akt][a].i;
			if (!navstiven[i]) {
				v.push_back(i);
			}
			if (v.size()==K) {
				break ;
			}
		}
		long double total = 0;
		map<int, long double> pst;
		for (int i : v) {
			pst[i] = pow(F[akt][i], alpha) * pow(B[akt][i], beta);
			total += pst[i];
		}
		double x = randdouble() * total;
		int dalsi = -1;
		for (int i : v) {
			x -= pst[i];
			if (x<0) {
				dalsi = i;
				break;
			}
		}
		navstiven[dalsi] = true; navstiveno++;
		res.push_back(dalsi);
		akt = dalsi;
	}
	return res;
}

vector<long double> delky_cest(vector<vector<int> > &mravenci) {
	vector<long double> L;
	for (int i=0; i<N; i++) {
		int akt = 0;
		for (int j=0; j<M; j++) {
			akt += dd[mravenci[i][j]][mravenci[i][(j+1)%M]];
		}
		L.push_back(akt);
		best = min(best, akt);
	}
	return L;
}

void vypust_feromony(vector<vector<int> > &mravenci, vector<long double> &L) {
	for (int i=0; i<N; i++) {
		for (int j=0; j<M; j++) {
			int a = mravenci[i][j];
			int b = mravenci[i][(j+1)%M];
			F[a][b] += 10000000.0 / (long double) L[i];
		}
	}
}

// Tuto funkci nepoužíváme, ale je to také možnost
void nacti_hladove() {
	int tmp;
	ifstream ifs("greedy.out");
	int k; ifs >> k >> tmp;
	vector<vector<int> > mravenci;
	for (int i=0; i<k; i++) {
		vector<int> m;
		for (int j=0; j<M; j++) {
			int x; ifs >> x;
			m.push_back(x);
		}
		mravenci.push_back(m);
	}
	ifs.close();
	vector<long double> L = delky_cest(mravenci);
	vypust_feromony(mravenci, L);
}

int main() {
	srand(123456789);
	// Nacti mesta
	ifstream ifs("obce-data.txt");
	int tmp;
	while (ifs >> tmp) {
		ifs >> mesta[M].x >> mesta[M].y;
		ifs.getline(line, 1024);
		M++;
	}
	ifs.close();
	// Spocitej vzdalenosti
	long double minD = 1000000000;
	long double maxD = 0;
	for (int i=0; i<M; i++) for (int j=i+1; j<M; j++) {
		dd[i][j] = dd[j][i] = sqrt(pow(mesta[i].x - mesta[j].x, 2) + pow(mesta[i].y - mesta[j].y, 2));
		D[i].push_back((Val){dd[i][j], j});
		D[j].push_back((Val){dd[j][i], i});
		B[i][j] = B[j][i] = F[i][j] = F[j][i] = 1000.0 / (long double)dd[i][j];
		minD = min(minD, dd[i][j]);
		maxD = max(maxD, dd[i][j]);
	}
	for (int i=0; i<M; i++) sort(D[i].begin(), D[i].end());
	cerr << "MinD = " << minD << ", MaxD = " << maxD << endl;

	// Nacti predpocitane hladove mravence
	//nacti_hladove();
	// Mravenci algoritmus
	for (int t=0; t<ITERACE; t++) {
		cerr << "Iterace " << (t+1) << ":" << endl;
		vector<vector<int> > mravenci;
		for (int i=0; i<N; i++) {
			//cerr << "Mravenec " << (i+1) << endl;
			mravenci.push_back(mravenci_cesta());
		}
		// Vaporizace
		for (int i=0; i<M; i++) for (int j=0; j<M; j++) F[i][j] *= (1.0-R);
		// Spocitej delky cest
		vector<long double> L = delky_cest(mravenci);
		// Vypust feromony
		vypust_feromony(mravenci, L);
		cout << best << endl;
	}

	return 0;
}