样例

输入

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

输出

6 4 7

输入

3 1
0 1 0
0 0 0
2 3 0

输出

1 -1

说明 在本题中，需要按照题目描述中的算法完成迪杰斯特拉算法，并在计算最短路径的过程中将每个顶点是否可达记录下来，直到求出每个可达顶点的最短路径之后，算法才能够结束。

迪杰斯特拉算法的特点是按照路径长度递增的顺序，依次添加下一条长度最短的边，从而不断构造出相应顶点的最短路径。

另外需要注意的是，在本题中为了更方便的表示顶点间的不可达状态，可以使用一个十分大的值作为标记。

来源

图论