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

#define SPOL 100
#define MEST 100

int cp[MEST][MEST][SPOL];		/* Cena za cestu z 1 do 2 společností 3 */
int cm[MEST][SPOL][SPOL];		/* Cena za překlad ve městě 1 od společnosti 2 ke společnosti 3 */

int cena[MEST][SPOL][2];		/* Jaká je cena za přesun do této části letiště? */
int konecne[MEST][SPOL][2];		/* Je výše uvedená cena konečná? */
int odkud_m[MEST][SPOL][2];		/* Jaký je předchozí uzel na cestě? */
int odkud_s[MEST][SPOL][2];
int odkud_b[MEST][SPOL][2];

int ns, nm;

#define INF 60000			/* Nekonečno */

 // Najdi prvek s~nejmenší dočasnou hodnotou (zde by se měla používat Fibonacciho halda).
int
findmin( int *m, int *s, int *b )
{
  int i,j,k;
  int mcena = INF;
  for (i=0; i<nm; i++)
    for (j=0; j<ns; j++)
      for (k=0; k<2; k++)
	if (!konecne[i][j][k] && (cena[i][j][k] < mcena)) {
	  mcena = cena[i][j][k];
	  *m=i; *s=j; *b=k;
	}
  return mcena;
}

 // Zkus použít nové spojení z [om,os,ob] do [m,s,b] za cenu c
void
zlepsi( int m, int s, int b, int c, int om, int os, int ob )
{
  if (cena[m][s][b] > c) {
    cena[m][s][b] = c;
    odkud_m[m][s][b] = om;
    odkud_s[m][s][b] = os;
    odkud_b[m][s][b] = ob;
  }
}

 // Získej od uživatele nějaká vstupní data.
void
input( void )
{
  int i,j,k;
  printf( "Zadej pocet spolecnosti, pocet mest:\n" );
  scanf( "%d%d", &ns, &nm );
  for (i=0; i<nm; i++)
    for (j=0; j<nm; j++) 
      for (k=0; k<ns; k++) {
	if (i==j) { cp[i][j][k] = 0; continue; }
	printf( "Cena za cestu z %d do %d spolecnosti %d:\n", i,j,k );
	scanf( "%d", &cp[i][j][k] );
    }
  for (i=0; i<nm; i++)
    for (j=0; j<ns; j++) 
      for (k=0; k<ns; k++) {
	if (j==k) { cm[i][j][k]=0; continue; }
	printf( "Cena za preklad ve meste %d od spolecnosti %d k %d:\n", i,j,k );
	scanf( "%d", &cm[i][j][k] );
      }
}

 // Nějaký prvek získal konečnou hodnotu, zkus použít cesty z něj.
void
updateokoli( int m, int s, int b )
{
  int i;
  int c = cena[m][s][b];
  if (!b)
    for (i=0; i<ns; i++)
      zlepsi(m,i,1, c+cm[m][s][i], m,s,b );
  if (b)
    for (i=0; i<nm; i++)
      zlepsi(i,s,0, c+cp[m][i][s], m,s,b );
}

 // Nainicializuj vstupní data
void
init(void)
{
  int i,j,k;
  for (i=0; i<nm; i++)
    for (j=0; j<ns; j++) {
      cena[i][j][0] = cena[i][j][1] = INF;
      konecne[i][j][0] = konecne[i][j][1] = 0;
    }
  for (i=0; i<ns; i++) {
    cena[0][i][0]=0;
    konecne[0][i][0]=1;
    updateokoli(0,i,0);
  }
}

 // Vypiš cestu
int
vypis( int m, int s, int b )
{
  printf( "Mesto %d, spolecnost %d, cast %d, (az sem to stalo %d penez)\n", m, s, b, cena[m][s][b] );
  if (!m) return;
  vypis( odkud_m[m][s][b], odkud_s[m][s][b], odkud_b[m][s][b] );
}

int
main( void )
{
  input();
  init();
  while(1) {
    int m, s, b;
    if (findmin(&m, &s, &b) == INF) {
      printf( "Do ciloveho mesta se nelze dostat.\n" );
      return 0;
    }
    konecne[m][s][b] = 1;
    if (m == nm-1) {
      printf( "Do ciloveho mesta se lze dostat za %d penez.\nCesta (pozpatku) je:\n", cena[m][s][b] );
      vypis(m,s,b);
      return 0;
    }
    updateokoli(m,s,b);
  }
  return 0;
}