Shortest Path from a Source

Special for beginners, ^_^

Problem Description

Given a directed graph $G=(V,E)$ and a source vertex $v_0\in V$, write a program that outputs the shortest paths from $v_0$ to every other vertex in $G$. Negative edge weights are allowed, as long as the total weight of every directed cycle is positive. Vertices are numbered from $1$ to $n$ ($n$ is the number of vertices in $G$).

Input Format

Line $1$: a positive integer $n$ ($2\le n\le80$), the total number of vertices in $G$.

Line $2$: an integer, the source $v_0$ ($v_0\in V$; $v_0$ may be any vertex in $G$).

Lines $3$ through $n+2$: the graph is given by an adjacency matrix $W$. Path lengths are less than $10^{15}$.

Output Format

$n-1$ lines in total, ordered by increasing vertex number. Each line outputs the shortest distance from the source $v_0$ to one vertex. Follow the sample for the exact format of each line.

Sample Input 1

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

Sample Output 1

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

Hint

Constraints

1s, 1024KiB for each test case.