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

#define ABS(X) ((X<0)?(-X):(X))
#define SQR(X) ((X)*(X))


#define INFILE "ontherun.in"
#define INFTY  INT_MAX

FILE *fin;
int caseno=0;

int flights, cities ;
int d[10][10], c[10][10][30], visited[10][10][30],best ;

struct entry { int city, flight, cost ; } ;

#define QSIZE 100000
int head, tail ;
entry Q[QSIZE] ;

void qinit() {
  head = tail = 0 ;
}

int qisempty() {
  return head == tail ;
}

void qpush(entry e) {
  Q[tail] = e ;
  tail++ ;
  tail %= QSIZE ;
}

void qget(entry *e) {
  *e = Q[head] ;
  head++ ;
  head %= QSIZE ;
}

int mflights, target ;
int mon[10][1000] ;

void visit(int from, int to, int f, int oc) {
  int time =  f%(d[from][to]) ;
  // int cost = c[from][to][time] ;
  // if (!cost || oc+cost>=best) { return ; }
  int cost = c[from][to][time] ;
  if (!cost) { return ; }
  cost += oc ;
  if ((mon[to][f]<=cost) || (cost>=best)) {
    return ;
  }
  if (f==mflights) {
    if ((to==target) && (cost < best)) { best = cost ; }
    return ;
  }
  mon[to][f] = cost ;
  entry pos = { to, f, cost } ;
  qpush(pos) ;
}


void solvecase(){
  entry pos = {0, -1, 0 };
  best = INFTY ;
  qinit() ;
  target = cities - 1 ;
  mflights = flights - 1;
  for (int j=0; j<10; j++) {
    for (int k=0; k<1000; k++) {
      mon[j][k] = INFTY ;
    }
  }
  qpush(pos) ;
  while (!qisempty()) {
    qget(&pos) ;
    if (pos.cost > mon[pos.city][pos.flight]) { continue ; }
    for (int i=0; i<cities; i++) {
      if (i==pos.city) { continue ; }
      visit(pos.city, i, pos.flight+1, pos.cost) ;
    }
  }
  if (best==INFTY) {
    printf("No flight possible.\n\n") ;
  } else {
    printf("The best flight costs %d.\n\n",best) ;
  }
}

int readcase(){
  fscanf(fin,"%i%i",&cities,&flights) ;
  for (int i=0; i<cities; i++) {
    for (int j=0; j<cities; j++){
      if (i==j) { continue ; }
      fscanf(fin,"%i",&(d[i][j])) ;
      for (int k=0; k<d[i][j]; k++) {
	fscanf(fin,"%i", &(c[i][j][k])) ;
        visited[i][j][k] = !(c[i][j][k]) ;
	//printf("cost %d->%d at %d: %d\n",i,j,k,c[i][j][k]);
      }
    }
  }
  return cities || flights ;
}

int main(){
 fin=fopen(INFILE,"r");

 while(readcase()){
   caseno++ ;
   printf("Scenario #%d\n",caseno) ;  
   solvecase();
 }

 fclose(fin);
 return 0;
}