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

#define MAXN 100
#define NEKONECNO 100000

struct bod
{
  int x, y;		/* Souřadnice bodu.  */
  int cislo;		/* Číslo bodu v pořadí podél obvodu mnohoúhelníka.  */
};

static int N;

static struct bod body[MAXN];
static int vzdalenost[MAXN][MAXN];


static int L[MAXN][MAXN][2];  /* Pole $L(u,v,x)$: $L[u][v][0]$ pokud $x=u$, $L[u][v][1]$ pokud $x=v$. */
static int predposledni[MAXN][MAXN][2];  /* Předposlední vrchol cesty, indexováno jako L.  */

static int porovnej_smery(const void *a, const void *b)  /* Porovná směry vektoru od bodu $a$ k $body[0]$ */
{                                                         /* a od bodu $b$ k $body[0]$.  */
  const struct bod *ba = a;
  const struct bod *bb = b;
  int dxa, dya, dxb, dyb;

  dxa = ba->x - body[0].x;
  dya = ba->y - body[0].y;
  dxb = bb->x - body[0].x;
  dyb = bb->y - body[0].y;

  return -(dxa * dyb - dya * dxb);
}

static void nacti(void)  /* Načte body a vzdálenosti a setřídí body podle */
{                         /*  pořadí podél obvodu mnohoúhelníka. */
  int u, v, l;

  scanf("%d", &N);

  for (v = 0; v < N; v++)
    {
      scanf("%d%d", &body[v].x, &body[v].y);
      body[v].cislo = v;
    }

  qsort(body + 1, N - 1, sizeof(struct bod), porovnej_smery);

  for (u = 0; u < N; u++)
    for (v = 0; v < N; v++)
      vzdalenost[u][v] = NEKONECNO;

  while (scanf("%d%d%d", &u, &v, &l) == 3)
    vzdalenost[u - 1][v - 1] = vzdalenost[v - 1][u - 1] = l;
}

static void rozsir_usek(int u, int v, int dalsi, int *delka, int *predp)  /* Rozšíří nejlepším způsobem interval */
{                                                                          /* $\left <u,v\right >$ přidáním dalšího vrcholu cesty \<dalsi>. */
  int cislo_u = body[u].cislo;                                             /* Délku rozšířené cesty uloží do \<delka> */
  int cislo_v = body[v].cislo;                                             /* a index předposledního vrcholu do \<predp>. */
  int cislo_dalsi = body[dalsi].cislo;
  int lu, lv;

  if (L[u][v][0] == NEKONECNO || vzdalenost[cislo_u][cislo_dalsi] == NEKONECNO)
    lu = NEKONECNO;
  else
    lu = L[u][v][0] + vzdalenost[cislo_u][cislo_dalsi];

  if (L[u][v][1] == NEKONECNO || vzdalenost[cislo_v][cislo_dalsi] == NEKONECNO)
    lv = NEKONECNO;
  else
    lv = L[u][v][1] + vzdalenost[cislo_v][cislo_dalsi];

  if (lu < lv)
    {
      *delka = lu;
      *predp = u;
    }
  else
    {
      *delka = lv;
      *predp = v;
    }
}

static void vypln_polozku(int u, int v, int z)  /* Vyplní $L[u][v][z]$.  */
{
  int u1, v1;

  u1 = (u + 1) % N;
  v1 = (v + N - 1) % N;

  if (z)
      rozsir_usek(u, v1, v, &L[u][v][z], &predposledni[u][v][z]);       /* Určujeme $L(u,v,v)$.  */
  else
      rozsir_usek(u1, v, u, &L[u][v][z], &predposledni[u][v][z]);      /* Určujeme $L(u,v,u)$.  */
}




static void vypln_L(void)  /* Vyplní tabulku $L$. */
{
  int u, v, l, z;

  for (v = 0; v < N; v++)
    {
      L[v][v][0] = L[v][v][1] = 0;
      predposledni[v][v][0] = predposledni[v][v][1] = -1;
    }

  for (l = 1; l < N; l++)
    for (u = 0; u < N; u++)
      {
	v = (u + l) % N;
	for (z = 0; z < 2; z++)
	  vypln_polozku(u, v, z);
      }
}

static void vypis_cestu(int u, int v, int x)  /* Vypíše cestu pokrývající interval $\left< u, v \right>$ */
{                                              /* a končící vrcholem $x$ ($x$ je buď $u$ nebo $v$).  */
  int z, predp;
  int u1, v1;

  u1 = (u + 1) % N;
  v1 = (v + N - 1) % N;

  z = (v == x);
  predp = predposledni[u][v][z];
  if (predp == -1)
    {
      printf("%d", body[x].cislo + 1);
      return;
    }
      
  if (z)
    vypis_cestu(u, v1, predp);
  else
    vypis_cestu(u1, v, predp);

  printf(" %d", body[x].cislo + 1);
}


int main(void)  /* Hlavní program.  */
{
  int v, minv, min;

  nacti();
  vypln_L();

  min = L[0][N - 1][0];
  minv = 0;
  for (v = 1; v < N; v++)
    if (L[v][v - 1][0] < min)
      {
	min = L[v][v - 1][0];
	minv = v;
      }

  if (min == NEKONECNO)
    printf("Cesta neexistuje.\n");
  else
    {
      printf("Cesta mající délku %d:\n", min);
      vypis_cestu(minv, (minv + N - 1) % N, minv);
      printf("\n");
    }

  return 0;
}