590

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <cstdlib>

#define INF 1000000000
#define ll long long

using namespace std;
int n,k;
int flight_schedule_cost[11][11][40];//flight_schedule_cost[city][tocity][dayno]=cost of that day frm ct1 to cty 2
int periodOfCity[11][11];
ll dp[1010][15];//ll dp[day][citypath];

int kase=1;

int costFromTheCity(int day,int startCity,int destination_city)
{
	int schedulePeriod = periodOfCity[startCity][destination_city];
	int dayOfschedule = day%(schedulePeriod);
	if(dayOfschedule==0)
		dayOfschedule=schedulePeriod;
	return flight_schedule_cost[startCity][destination_city][dayOfschedule];
}
ll DP(int day,int city)
{
	ll d;
	int cost;
	dp[1][1]=0;
	for(int i=1;i<=n;i++)
		dp[2][i]= (flight_schedule_cost[1][i][1]==0?INF : flight_schedule_cost[1][i][1]);
	for(int i=3;i<=(k+1);i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int kk=1;kk<=n;kk++)
			{
				if(j==kk)
					continue;
				if(dp[i-1][kk]==INF)
					continue;
				cost = costFromTheCity(i-1,kk,j);
				if(cost==0)
					continue;
				dp[i][j] = (dp[i-1][kk]+cost < dp[i][j] ? dp[i-1][kk]+cost : dp[i][j]);
			}
		}
	}
	return dp[k+1][n];
}
int main()
{
	int dailyCost;

	while(scanf("%d%d",&n,&k),n+k)
	{
		memset(flight_schedule_cost,0,sizeof(flight_schedule_cost));
		memset(periodOfCity,0,sizeof(periodOfCity));
		memset(dp,INF,sizeof(dp));
		for(int i=0;i<1010;i++)
			for(int j=0;j<15;j++)
				dp[i][j]=INF;
		for(int start_city=1;start_city<=n;start_city++)
		{
			for(int destination_city=1;destination_city<=n;destination_city++)
			{
				if(destination_city==start_city)
				continue;
				scanf("%d",&periodOfCity[start_city][destination_city]);
				for(int dayNo=1;dayNo<=periodOfCity[start_city][destination_city];dayNo++)
				{
					scanf("%d",&dailyCost);
					flight_schedule_cost[start_city][destination_city][dayNo]=dailyCost;
				}
			}
		}
		ll tmp = DP(k+1,n);
		if(tmp!=INF)
		{
			printf("Scenario #%d\n",kase++);
			printf("The best flight costs %lld.\n\n",tmp);
		}
		else
		{
			printf("Scenario #%d\n",kase++);
			printf("No flight possible.\n\n");
		}
	}
	return 0;
}