描述
   Flute市的phlharmoniker乐团是一只非常优秀的管弦乐团,一直以来在国际古典乐坛上有着很高的地位.2000年的乐季又开始了,乐团在音乐总监cmr和乐团指挥lym的带领下到harp市作一次大型演出.本着普及古典音乐的目的,lym决定在到达harp市之前先在周围的一些城市作一段时间的巡回演出.此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另外一个城市,最后才到达目的地harp市。请注意，由于乐团的演奏风格多样，适合演出的曲目很多，所以乐团可以多次来到同一个城市进行演出。
   虽然演出酬劳相当可观，但还是要精打细算，尽量减少路费。可这并不容易，由于航线的费用和班次每天都在变。城市与城市之间都有一份循环的航班表，每一时间，每一方向航班表循环的周期都可能不同。
   经过一个晚上的思考，我们的音乐家终于想出了预定机票的最佳方案。你知道他们是怎么做的吗？
代号
troupe
输入格式 (文件名: troupe.in)
   输入文件包含若干各场景。每各场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始。音乐家们要在这n各城市里作巡回演出，时间是k天。城市用1，2，3，4，….   n 编号,期中1是起点flute市，n是终点harp市。接下来将有n*(n-1) 份航班表，一份航班表就是一行，描述每对城市之间的航线和价格。第一组n-1份航班表对应从城市1到其他所有城市（2，3，4，5，…  ,n）的航班，接下来的n-1行是从城市2到其他所有城市（1，3，4，5，…, n）的航班情况。如此下去。
    每份航班表由一个整数d (1<=d<=30) 开始，表示航班表循环的周期。接下来的d个非负整数，表示1，2，3，…  ,d 天对应的两个城市的航班的价格。价格为0表示那天两个城市之间没有航班。
    例如：航班表 “3  75  0  80”表示第一天的机票是75 koi (koi 是信息学竞赛专用货币单位)，第2 天没有航班，第3天的机票是80  koi ,然后是循环，第4天又是75 koi ,第5天没有航班，第6天的机票是80，如此循环。
    输入文件由n=k=0的场景表示结束。
输出格式 (文件名: troupe.out)
    对输入的每各场景如果乐团可能从城市1出发，每天都要飞往另外一个城市，最后（经过k天）抵达城市n，则输出这k个航班的价格之和的最小值。如果不可能存在这样的巡回演出路线，则输出0.
限制
2<=n<=10
1<=k<=1000
1<=d<=30
比较器
合并连续空白字符
样例数据 1
输入数据
3  6
2  130  150
3  75  0  80
7  120  110  0  100  110  120  0
4  60  70  60  50
3  0  135  140
2  70  80
2  3
2  0  70  
1  80  
0  0
输出数据
460
0