/* KSP 18-3-4 řešení dle Programátorské kuchařky -- Dijkstrův algoritmus s haldou */

#include <stdio.h>

#define MaxN 100
#define MaxM 100
#define MaxK 50

typedef struct policko_typ {
  int x,y,vzdal,je_docas,predx,predy; // souřadnice, vzdálenost, zda je dočasné, předchůdce
}policko;

typedef struct pravidlo_typ {         // možné pohyby čuněte
  int x,y,namaha;                     // posun o x, posun o y, vynaložená námaha
}pravidlo;

typedef struct uzel_typ {             // uzel v haldě
  int vzdal,x,y;                      // dočasná vzdálenost, souřadnice
}uzel;

int N,M,K;                            // rozměry lesa, počet pravidel
pravidlo pravidla[MaxK];              // všechny pohyby čuněte
uzel halda[MaxN*MaxM*MaxK];           // halda na políčka           
int halda_len;                        // velikost haldy
policko les[MaxN][MaxM];              // dvojrozměrný prostor = les
  
void halda_vloz(int x, int y, int vzdal) {
  int i;
  uzel pom;
  
  printf("Davam na haldu [%d, %d]: %d\n",x,y,vzdal);
  i = halda_len;
  halda_len++;
  halda[i].x = x; halda[i].y = y; halda[i].vzdal = vzdal;
  while (i > 1 && halda[i/2].vzdal > halda[i].vzdal) {
    pom = halda[i/2];
    halda[i/2] = halda[i];
    halda[i] = pom;
    i = i/2;
  } 
}

void halda_odeber_min() {
  int i, j;
  uzel pom;
  halda[1] = halda[halda_len];
  halda_len--;
  i = 1;
  while (2*i<=halda_len) {
    j = i;
    if (halda[j].vzdal > halda[2*i].vzdal) j = 2*i;
    if (2*i+1 <= halda_len && halda[j].vzdal > halda[2*i+1].vzdal) j = 2*i+1;
    if (i == j) break;
    pom = halda[i]; halda[i] = halda[j]; halda[j] = pom;
    i = j;
  } 
}

void dijkstra(int start_x, int start_y, int cil_x, int cil_y) {
  int vx, vy, nx, ny, i, j;         
  
  for (i = 0; i < N; i++) {           // inicializace
    for (j = 0; j < M; j++) {
      les[i][j].je_docas = 1;       
      les[i][j].vzdal = -1;           
      les[i][j].predx = les[i][j].predy = -1;           
    }
  }
  les[start_x][start_y].vzdal = 0;    // vzdálenost start-start je 0
  halda_vloz(start_x, start_y, 0);    // start na haldu
  
  while (halda_len > 0) {             // dokud není halda prázdná 
    vx = halda[0].x;                  // vybereme políčko s nejmenší dočasnou vzdáleností
    vy = halda[0].y;
    printf("Odebiram z haldy [%d, %d]: %d\n",vx, vy, halda[0].vzdal);
    halda_odeber_min();               // odebereme políčko z haldy
    if (vx == cil_x && vy == cil_y) break;    // bukvice nalezena, konec
    if (!les[vx][vy].je_docas) {
      printf("Tady uz jsme jednou byli.\n");
      continue;     // tady uz jsme byli, jdeme dál
    }
    les[vx][vy].je_docas = 0;                 // políčko prohlásíme za trvalé

    for (i = 0; i < K; i++) {         
      nx = pravidla[i].x + vx;                // kam se odsud umíme dostat s pravidlem i
      ny = pravidla[i].y + vy;
      printf("Zkousim nove policko [%d, %d]\n",nx,ny);
      if (nx < N && ny < M && nx >=0 && ny >= 0)  // nevyběhli jsme z lesa
        if ((les[nx][ny].vzdal == -1) || 
            (les[nx][ny].vzdal > les[vx][vy].vzdal + pravidla[i].namaha)) {
          les[nx][ny].vzdal = les[vx][vy].vzdal + pravidla[i].namaha;   // nová vzdálenost
          les[nx][ny].predx = vx;                                       // nový předek
          les[nx][ny].predy = vy;
          halda_vloz(nx,ny,les[nx][ny].vzdal);                          // vlož na haldu
        }
    }
  }
}

int main() {
  int prase_x, prase_y, bukv_x, bukv_y;           
  int nx, ny, i;
  
  printf("Rozměry lesa: "); scanf ("%d %d", &N, &M);
  printf("Pozice prasete: "); scanf("%d %d", &prase_x, &prase_y);
  printf("Pozice bukvice: "); scanf("%d %d", &bukv_x, &bukv_y);
  printf("Počet pravidel pohybu prasete: "); scanf("%d", &K);
  for (i = 0; i < K; i++) scanf("%d %d %d",&pravidla[i].x,&pravidla[i].y,&pravidla[i].namaha);
  
  dijkstra(prase_x, prase_y, bukv_x, bukv_y);

  if (les[bukv_x][bukv_y].vzdal == -1) printf("Cesta neexistuje.\n");
  else {
    printf("Nejkratší cesta pozpátku: \n");
    nx = bukv_x; ny = bukv_y;
    while (nx != -1 && ny != -1) {
      printf("[%d, %d]\n",nx,ny);
      nx = les[nx][ny].predx; ny = les[nx][ny].predy;
    }
  }
  return 0;
}