1835. [国家集训队2011]大楼

【题目描述】

xz是一个旅游爱好者，这次他来到了一座新的城市。城市中央有一幢高耸入云的大楼。这幢楼到底有多少层呢？据说和非负整数的个数是一样多的。xz想爬上这座大楼来观赏新城市的全景。

这幢大楼的楼层从下至上用从小到大的非负整数编号。每层楼有n个房间，用1到n的正整数编号。楼层之间用电梯连接，电梯只能上行，不能下行或者同层移动。（下楼一般自行解决）电梯用(u,v,w)的形式给出，表示对于任意正整数i，有第i层的房间u到第i + w层的房间v有一部电梯。电梯只能从起点开往终点，不能中途停留。

xz想要观赏城市全景，至少需要登上第m层楼，即最终需要到达的楼层数 ≥ m。由于乘坐电梯要缴纳高额的费用，而如果花销太大回家就没法报账了，xz希望乘坐电梯的次数最少。现在xz在第0层的1号房间，你需要求出这个最少的乘坐次数。

【输入格式】

第一行包含一个正整数T，表示数据的组数。接下来的数据分为T个部分。

每个部分第一行包含两个正整数n和m，意义见题目描述。

接下来n行，每行包含n个非负整数。这n行中，第i行第j个数为wi,j，如果wi,j非零，则表示有电梯(i,j,wi,j)。

同一行各个数之间均用一个空格隔开。

【输出格式】

对于每组数据，输出一行一个正整数，最少的乘坐次数。

【样例输入】

2

6 147

0 1 0 50 0 0

0 0 1 0 0 0

20 0 0 0 0 0

0 0 0 0 1 50

0 0 0 8 0 0

0 0 0 0 0 3

6 152

0 1 0 50 0 0

0 0 1 0 0 0

20 0 0 0 0 0

0 0 0 0 1 50

0 0 0 8 0 0

0 0 0 0 0 3

【样例输出】

9

10

【提示】

第一组数据中，使用电梯的顺序为1→2→3→1→2→3→1→4→6→6；第二组数据中，使用电梯的顺序为1→2→3→1→2→3→1→4→5→4→6。第二组数据最后到达了153层，但是没有更短的路径使得恰好到达152层，因此答案为10。

有如下几类具有特点的数据：

1. 有10%的数据所有的n = 2；

2. 有20%的数据m ≤ 3000；

3. 有20%的数据对于满足1 ≤ i, j ≤ n的整数i和j，若wi,j ≠ 0，则有wi,j ≥ 10^15；

4. 有30%的数据所有的n = 40。

以上各类数据均不包含其他类数据。

对于所有数据T = 5，1 ≤ n ≤ 100，1 ≤ m ≤ 10^18；对于满足1 ≤ i,j ≤ n的整数i和j，有0 ≤ wi,j ≤ 10^18。

数据保证能够到达m层或更高的楼层。