// Arup Guha
// 12/5/2023
// Solution to COP 3502 Final Exam Part A - Friday Version (Section 1)

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

long long mandist(long long* pt1, long long* pt2);
int randnum(int max);

int main() {

    srand(time(0));

    // Read in # of points.
    int n;
    scanf("%d", &n);

    // Allocate space to store each point.
    long long** pts = calloc(n, sizeof(long long*));
    for (int i=0; i<n; i++) pts[i] = calloc(2, sizeof (long long));

    // Read in each point.
    for (int i=0; i<n; i++)
        scanf("%lld%lld", &pts[i][0], &pts[i][1]);

    // Initialize # of unvisited places. Index 0 is already visited.
    int left = n-1;

    // Store unused places here.
    int* unused = calloc(n-1, sizeof(int));
    for (int i=1; i<n; i++) unused[i-1] = i;

    // Print index of first location visited.
    printf("0");

    // Set up accumulator and current location.
    int curI = 0;
    long long res = 0;

    // Take n-1 trips.
    for (int i=0; i<n-1; i++) {

        // Index into the unused array.
        int rndIdx = randnum(left);

        // Index into the point array that we're going to next.
        int nextI = unused[rndIdx];

        // Print it.
        printf(" %d", nextI);

        // Add in the manhattan distance for this trip.
        res += mandist(pts[curI], pts[nextI]);

        // If we copy the last item into this location, we copy over
        // the used item with something that is unused (usually).
        unused[rndIdx] = unused[left-1];

        // Update our current location for the next iteration.
        curI = nextI;

        // One fewer unvisited location.
        left--;
    }

    // Finish output.
    printf("\n");
    printf("%lld\n", res);

    // Free stuff.
    for (int i=0; i<n; i++)
        free(pts[i]);
    free(pts);
    free(unused);

    return 0;
}

long long mandist(long long* pt1, long long* pt2) {
    return abs(pt1[0]-pt2[0]) + abs(pt1[1]-pt2[1]);
}

int randnum(int max) {
    return ( (rand()<<15) + rand())%max;
}