题目描述

在带权有向图 $G$ 中，给定一个源点 $v$，求从 $v$ 到 $G$ 中的其余各顶点的最短路径问题，叫做单源点的最短路径问题。迪杰斯特拉算法是常用的一种，按照路径长度递增的次序产生最短路径。

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

输入格式

第一行包含两个正整数 $n$ 和 $s$，表示图中共有 $n$ 个顶点，且源点为 $s$。

接下来的 $n$ 行，每行包含 $n$ 个用空格隔开的整数。对于第 $i$ 行的第 $j$ 个整数：

• 若大于 $0$，则表示第 $i$ 个顶点有指向第 $j$ 个顶点的有向边，且权值为该整数值；
• 若为 $0$，则表示没有从 $i$ 指向 $j$ 的有向边。

当 $i=j$ 时，该整数保证为 $0$。

输出格式

输出一行，包含 $n-1$ 个整数，按照顶点编号从小到大的顺序，依次输出源点到除源点外每个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，则输出 $-1$。

整数之间用一个空格隔开，行末无多余空格，结尾有换行。

样例

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

6 4 7

数据范围

$2\le n\le 50$

$2\le s\le n$

权值为整数，满足 $0\le$ 权值 $\le 100$

来源

最短路径