题目描述

在带权有向图 $G$ 中，给定一个源点 $v$，求从 $v$ 到 $G$ 中的其余各顶点的最短路径问题，叫做单源点的最短路径问题。

在常用的单源点最短路径算法中，迪杰斯特拉算法是最为常用的一种，是一种按照路径长度递增的次序产生最短路径的算法。

在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出源点至每一个其它顶点的最短路径长度。

输入格式

输入的第一行包含 $2$ 个正整数 $n$ 和 $s$，表示图中共有 $n$ 个顶点，且源点为 $s$（$2 \le s < n \le 50$）。

以后的 $n$ 行中每行有 $n$ 个用空格隔开的整数。对于第 $i$ 行的第 $j$ 个整数，如果大于 $0$，则表示第 $i$ 个顶点有指向第 $j$ 个顶点的有向边，且权值为对应的整数值（$0 \le$ 权值 $\le 100$）；如果这个整数为 $0$，则表示没有 $i$ 指向 $j$ 的有向边。当 $i$ 和 $j$ 相等的时候，保证对应的整数为 $0$。

输出格式

只有一行，共有 $n-1$ 个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出 $-1$。

请注意行尾输出换行。

样例 #1

样例输入 #1

4 2
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0

样例输出 #1

6 4 7