/* SWERC'97 - Always on the run */
/*  11/7/97 - Matthias Ruhl     */

#include <stdio.h>

#define MAXPERIOD 30
#define MAXCITIES 10

FILE *inp;
struct
{
  int period;
  int cost[MAXPERIOD];
} conn[MAXCITIES][MAXCITIES];


int process()
{
  int i,j,n,k,l,c,mincost[MAXCITIES],newcost[MAXCITIES];
  static int caseno = 1;

  fscanf(inp,"%d %d",&n,&k);
  if(n == 0 && k == 0) return 0;

  /* read in connections */
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      if(i != j)
	{
	  fscanf(inp,"%d",&conn[i][j].period);
	  for(l=0;l<conn[i][j].period;l++)
	    fscanf(inp,"%d",conn[i][j].cost+l);
	}
  /* compute path */
  mincost[0] = 0;
  for(i=1;i<n;i++) mincost[i] = -1;
  for(i=0;i<k;i++)
    {
      for(j=0;j<n;j++)
	{
	  newcost[j] = -1;
	  for(l=0;l<n;l++)
	    if(l != j && mincost[l] != -1)
	      {
		c = conn[l][j].cost[i%conn[l][j].period];
		if(c && (newcost[j] == -1 || mincost[l] + c < newcost[j]))
		  newcost[j] = mincost[l] + c;
	      }
	}
      for(j=0;j<n;j++) mincost[j] = newcost[j];
    }
  printf("Scenario #%d\n",caseno++);
  if(mincost[n-1] == -1)
    printf("No flight possible.\n");
  else
    printf("The best flight costs %d.\n",mincost[n-1]);
  printf("\n");
  return 1;
}

int main()
{
  inp = fopen("ontherun.in","r");
  while(process());
  fclose(inp);
  return 0;
}