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

int numtimes[20][20];
int times[20][20][40];
int table[1100][20];

#define MAX(a, b) ((a>b)?a:b)
#define MIN(a, b) ((a<b)?a:b)
#define BIG 999999999

int 
gettime( int from, int to, int day )
{
int a = from, b = to;
int ret;
if (from==to) return BIG;
ret = times[a][b][ day % numtimes[a][b] ];
if (!ret) return BIG;
return ret;
}

int
main( void )
{
  FILE *in=fopen( "ontherun.in", "r" );
  int ixx;

  for( ixx=1; ; ixx++ ) {
       int n, k;
       int i,j,l;

       fscanf( in, "%d%d", &n, &k );
       if (!(n | k)) return 0;
       printf( "Scenario #%d\n", ixx );
       for( i=0; i<n; i++ )
	 for( j=0; j<n; j++ ) 
	   if (j!=i)
	     {
	       fscanf( in, "%d", &numtimes[i][j] );
	       for( l=0; l<numtimes[i][j]; l++ )
		 fscanf( in, "%d", &times[i][j][l] );
	     }

       for( j=0; j<n; j++ )
	 table[0][j]=BIG;
       table[0][0]=0;
	   
       for( i=1; i<k+1; i++ )
	 {
	 for( j=0; j<n; j++ )
	   table[i][j]=BIG;

	 for( j=0; j<n; j++ )
	   for( l=0; l<n; l++ ) 
	     {
	     int b = table[i-1][l] + gettime(l,j,i-1);
	     table[i][j] = MIN( table[i][j], b );
	     }
#if 0
	 printf( "Day %d: ", i );
	 for( j=0; j<n; j++ )
	   printf( "%d ", table[i][j] );
	 printf( "\n" );
#endif
         }
       if (table[k][n-1] == BIG)
	 printf( "No flight possible.\n" );
       else
	 printf( "The best flight costs %d.\n", table[k][n-1] );
       putchar( '\n' );
       }
}