小L与暑期课程(关键路径)
Time Limit: 1000 MSMemory Limit: 1000 KB

Description

幸福的暑假开始啦,小L想出去看看外面的世界。他兴高采烈地走到学校大门,一看手表现在是9:50。他突然想起来,今天似乎有暑期课程,而暑期课程正好在9:50上课!
小L不是神,他不知道从校门到教室需要多少时间,面对一个岔路口,他只会随机选一个岔路口走。
这可怎么办,小L掏出手机想给老师请几分钟的假,请假的时长在保证他一定从学校到教室的情况下,请假的时间最短。
现在需要你帮帮小L,算出他需要请假的时间。

Input

第一行一个int型整数T,代表一共有T组数据。
每组数据的第二行是一个整数n(n<=1000),表示地图有n个顶点。(节点从1开始标号)
接下来n行n列个数,第i行第j个数表示走i号节点到j号节点的这一条路径所需花的分钟数(如果该数为-1,表示此路不通)
校门位于1号点,教室位于n号点,地图中不会有环出现,且所有道路(u,v)可以走仅当序号u<v

Output

输出T行, 每行包括一个整数, 代表每组数据小L需要请假的时长

Sample Input

1
3
-1 1 2
-1 -1 3
-1 -1 -1

Sample Output

4
Submit Your Code                        Discuss



苏ICP备2022026913号-1