题目描述

给定一个有向带权图和源点 $v_0$。边权可以为负数，但保证每个有向环的边权和都为正数。请按顶点编号从小到大，输出源点到其他各顶点的最短距离。

输入格式

第一行一个整数 $n$。第二行一个整数 $v_0$。接下来 $n$ 行，每行 $n$ 个用空格分隔的项目，构成邻接矩阵。整数表示边权，单独的 - 表示不存在这条边；主对角线为 0。

输出格式

输出 $n-1$ 行，跳过源点。每行格式为 (源点->终点)=最短距离，不添加空格。

样例

5
1
0 2 - - 10
- 0 3 - 7
- - 0 4 -
- - - 0 5
- - 6 - 0

(1->2)=2
(1->3)=5
(1->4)=9
(1->5)=9

数据范围

• $2\le n\le80$，$1\le v_0\le n$。
• 边权为整数，绝对值不超过 $10^6$。
• 保证源点能到达每个顶点，且每个有向环的权值和为正。