#include <iostream>
#include <fstream>
#include <cmath>
#include <sstream>
using namespace std;

float cities[130][3];
float dist[130][130]; ///distance
float route[130];

int x, y;

float nearest_city( float distance[130][130] ) {
    for( int j = 0; j < 130; j++ ) {
        if ( dist[x][j] != 0 && cities[j][2] != 1 ) {
            if ( dist[x][j] < dist[x][y] )
                y = j;
        }
    }
    return y;
}

void fill_distance() {
   for( int i = 0; i < 130; i++ ) {
       for( int j = 0; j < 130; j++ ) {
           dist[i][j] = sqrt(pow(cities[j][0] - cities[i][0], 2) + pow(cities[j][1] - cities[i][1], 2));
       }
   }
}

int main() {
    float coor_x, coor_y, a;
    float sum = 0.0;
    float sum_help = 100000.0;

    ifstream file;
    file.open("ch130.tsp");
    file >> a;

    int i = 0;

    while( !file.eof() ) {
        file >> a >> coor_x >> coor_y;

        cities[i][0] = coor_x;
        cities[i][1] = coor_y;
        cities[i][2] = 0;

        i++;
    }

    fill_distance();



    for ( int i = 0; i < 130; i++ ) {
        cities[i][2] = 1;

        x = i;
        y = x + 1;

        for ( int k = 0; k < 129; k++ ) {

            nearest_city(dist);

            sum += dist[x][y];

            cities[y][2] = 1;

            x = y;

            for ( int l = 0; l < 130; l++ ) {
                if ( cities[l][2] != 1 )
                    y = l;
            }
        }
        sum += dist[x][i];


        for ( int c = 0; c < 130; c++ )
           cities[c][2] = 0;


        route[i] = sum;


        if ( sum < sum_help )
            sum_help = sum;

        sum = 0;
    }

    cout << "Najkrotsza trasa wynosi " << sum_help;

    for ( int z = 0; z < 130; z++ )
        if ( route[z] == sum_help )
            cout << " z miasta nr " << z + 1;
}