#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <limits.h>


int grafi[31][12][12];
int n,k;


int doit(int,int,int,int);

int main()
{	FILE *in;
	int t,j,k,d,mind,scen,app,i;


	in=fopen("ontherun.in","r");



	scen=1;
	while(1)
	{ fscanf(in,"%d %d ",&n,&k);
	  if(n==0 && k==0)
	   break;




	  for(t=0;t<n;t++)
	   for(j=0;j<n;j++)
	   { if(j==t)
	      continue;

	     fscanf(in,"%d ",&d);
	     grafi[0][t][j]=d;

	     for(i=1;i<=d;i++)
	      fscanf(in,"%d ",&(grafi[i][t][j]));
	   }


	   mind=doit(n,k,0,n-1);

	   printf("Scenario #%d\n",scen);
	   if(mind<INT_MAX)
	    printf("The best flight costs %d.\n",mind);
	   else
	    printf("No flight possible.\n");
	   scen++;



	}


	fclose(in);
	return 0;
}



int doit(int n,int k2,int start,int to)
{int day,t,min,h,maxint=INT_MAX,fine,flag,tempdistanzaminima,distanzaritorno,appday;

	int priorita[11];


	for(t=0;t<11;t++)
	{ priorita[t]=maxint;
	  
	}

	priorita[start]=0;


	distanzaritorno=maxint;

	min=start;

	for(day=0,fine=0;!fine;day++)
	{ tempdistanzaminima=maxint;

	 



	  for(h=0;h<n;h++)
	   if(priorita[h]<tempdistanzaminima)
	   { min=h;
	     tempdistanzaminima=priorita[h];
     	   }


	
	  if(min==to && day==k2)
	  { distanzaritorno=tempdistanzaminima;
	    fine=1;
	  }

	  flag=0;
	  for(t=0;t<n;t++)
	  { if(t==min)
	     continue;
   	    appday=day%grafi[0][min][t];
	   if(grafi[appday+1][min][t]>0 && day<(k2-1))
	    if(tempdistanzaminima+grafi[appday+1][min][t]<priorita[t])
	    { priorita[t]=tempdistanzaminima+grafi[appday+1][min][t];
	      flag=1;
	    }
	  }

	  if(!flag)
	   fine=1;

	  priorita[min]=maxint;

	  day++;





	}

	return distanzaritorno;






}