#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

#define dot pair<int, int>


vector< vector<double> > m; // массив длин промежуточных кратчайших путей
vector<dot> dots;           // массив координат точек
string s(80, '*');          // для красивой печати

// расстояние между точками
double distance(int a, int b) {
    return sqrt( pow((dots[b].first - dots[a].first), 2) + pow((dots[b].second - dots[a].second), 2) );
}

// печать матрицы m
void print_m() {
    for (int i = 0; i < m.size() - 1; i++) {
        for (int j = 0; j <= m.size(); j++) {
            cout.setf(ios::left);
            cout.width(8);
            cout << m[i][j] << " ";
        }
        cout << endl;
    }
}

// для сортировки массива координат по возрастанию x
bool cmp(const dot & d1, const dot & d2) {
    return d1.first != d2.first ? d1.first < d2.first : d1.second < d2.second;
}

int main(int argc, const char * argv[]) {
    freopen("/Users/Alexander/Dropbox/Университет/CS242/euclidean traveling-salesman problem/euclidean traveling-salesman problem/input.txt", "r", stdin);

    int n;
    cin >> n;
    int NumberOfPoints = n;

    // выделение памяти и заполнение матриц
    m.resize(n);
    for (int i = 0; i < n; i++)
        m[i].resize(n + 1);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        dots.push_back(make_pair(x, y));
    }
    sort(dots.begin(), dots.end(), cmp); // сортировка по х


    //cout << distance(0, 1) + distance(1, 3) + distance(3, 5) + distance(5, 7) + distance(7, 8) + distance(8, 6) + distance(6, 4) + distance(4, 2) + distance(2, 0) << endl; // ответ

    m[0][1] = distance(0, 1);

    // расстановка длин путей из каждой вершины в каждую
    for (int j = 2; j < NumberOfPoints; j++) {
        for (int i = 0; i <= j - 2; i++)
            m[i][j] = m[i][j - 1] + distance(j, j - 1);

        m[j - 1][j] = m[j-2][j - 1] + distance(j, j-2);

//        хз что это и зачем нужно вообще
//        for (int i = 1; i <= j - 3; i++)
//            if (m[j - 1][j] < m[i][j - 1] + distance(j, i))
//                m[j - 1][j] = m[i][j - 1] + distance(j, i);

//        print_m();
//        cout << endl << s << endl << endl;
    }

    // зацикливание пути, поиск его длины
    for (int i = 0; i < NumberOfPoints; i++)
        m[i][NumberOfPoints] = m[i][NumberOfPoints - 1] + distance(i, NumberOfPoints - 1);

    print_m();
    cout << endl << s << endl << endl;


    double minWay = INT32_MAX;
    for (int i = 0; i < NumberOfPoints - 1; i++)
        if (minWay > m[i][NumberOfPoints])
            minWay = m[i][NumberOfPoints];
    cout << minWay << endl;
}