언제나 도주 중

끼익거리는 타이어 소리, 사방을 훑는 탐조등, 요란한 사이렌, 곳곳에 깔린 경찰차. 트리샤 퀵핑거가 또 일을 냈다! '모나리자'를 훔치는 일은 계획보다 어려웠지만, 세계 최고의 미술품 도둑이라면 예상치 못한 일까지 예상해야 하는 법이다. 그렇게 그녀는 포장된 액자를 팔에 단단히 낀 채, 공항으로 향하는 북행 지하철을 타려고 달리고 있다.

그림을 실제로 훔치는 것보다 더 중요한 것은 곧 뒤쫓아 올 경찰을 따돌리는 일이다. 트리샤의 계획은 단순하다. 며칠 동안 하루에 한 번씩 이 도시에서 저 도시로 비행하다가, 경찰이 자신의 흔적을 놓쳤다고 충분히 확신하게 되면 애틀랜타로 날아가 '고객'(오직 '미스터 P.'로만 알려진 인물)을 만나 그림을 넘긴다.

문제는 요즘엔 값비싼 미술품을 훔칠 때조차 지출 예산을 신경 써야 한다는 점이다. 그래서 트리샤는 도주 항공편에 최대한 적은 돈을 쓰고 싶어 한다. 항공사 요금과 운항 여부가 날마다 달라지기 때문에 이는 쉽지 않다. 어떤 연결편의 요금과 운항 여부는 관련된 두 도시와 여행하는 날짜에 따라 정해진다. 순서가 있는 모든 도시 쌍에는 며칠마다 반복되는 운항 시간표가 있으며, 주기의 길이는 도시 쌍마다, 그리고 방향마다 다를 수 있다.

트리샤는 그림을 훔치는 데는 능하지만 항공편을 예약할 때는 쉽게 헷갈린다. 바로 여기서 당신이 필요하다.

입력은 여러 개의 시나리오로 이루어진다.

각 시나리오는 두 정수 $n$과 $k$가 적힌 줄로 시작한다. $n$은 트리샤의 도주 경로에 등장할 수 있는 도시의 수이고, $k$는 그녀가 타게 될 비행 횟수이다. 도시는 $1, 2, \ldots, n$으로 번호가 매겨지며, 도시 $1$이 출발지, 도시 $n$이 최종 목적지이다. 값의 범위는 $2 \le n \le 10$, $1 \le k \le 1000$이다.

이어서 서로 다른 모든 순서쌍의 도시 사이 연결을 설명하는 $n(n-1)$개의 운항 시간표가 한 줄에 하나씩 주어진다. 처음 $n-1$개는 도시 $1$에서 다른 모든 도시($2, 3, \ldots, n$)로 가는 항공편, 다음 $n-1$개는 도시 $2$에서 다른 모든 도시($1, 3, 4, \ldots, n$)로 가는 항공편, 이런 식으로 이어진다.

각 운항 시간표는 주기의 길이(일수) $d$로 시작하며 $1 \le d \le 30$이다. 그 뒤에는 $1, 2, \ldots, d$일째의 항공편 요금을 나타내는 $d$개의 음이 아닌 정수가 온다. 요금이 $0$이면 그날은 해당 항공편이 없다는 뜻이다.

예를 들어 시간표 3 75 0 80은 $1$일째에는 요금이 $75$, $2$일째에는 항공편이 없음, $3$일째에는 요금이 $80$임을 뜻하며, 이후 주기가 반복되어 $4$일째에는 다시 $75$, $5$일째에는 항공편이 없는 식으로 이어진다.

입력의 끝은 $n = k = 0$인 시나리오로 표시되며, 이 시나리오는 처리하지 않는다.

각 시나리오마다 먼저 시나리오 번호를 Scenario #i 형식으로 출력한다. 여기서 $i$는 $1$부터 시작하는 시나리오 순번이다.

트리샤는 도시 $1$에서 출발한다. $k$일 동안 매일 현재 있는 도시와 다른 도시로 비행한다. 정확히 $k$번의 비행 후에 도시 $n$에 도착하는 것이 가능하면 The best flight costs x.를 출력한다. 여기서 $x$는 $k$번의 비행에 드는 최소 총비용이다. 그렇게 이동하는 것이 불가능하면 No flight possible.을 출력한다.

연속한 두 시나리오 사이에는 빈 줄을 하나 넣어 구분한다.