Floyd-Warshall: Shortest Path in a Graph

You are given a weighted directed graph with N cities represented by an adjacency matrix. The entry in the matrix at row i and column j represents the weight of the direct road from city i to city j. A value of -1 represents that there is no direct road between these cities (except that the diagonal elements are always 0).

Your task is to determine the shortest distance from a specified start city to an end city using the Floyd-Warshall algorithm. If no route exists, output "No path exists".

The algorithm follows the recurrence: \[ dist[i][j] = \min\left(dist[i][j],\, dist[i][k] + dist[k][j]\right) \quad \text{for each } k \]

Implement the algorithm so that it can process input from stdin and output the result to stdout.

inputFormat

The input is read from stdin in the following format:

N
row1
row2
... 
rowN
start end

Where:

• N is the number of cities.
• Each of the next N lines contains N space-separated integers representing a row of the adjacency matrix. A value of -1 indicates no direct road (except on the diagonal which is always 0).
• The last line contains two space-separated integers: the start city and the end city (0-indexed).

outputFormat

The output should be written to stdout. It is either the shortest distance (an integer) from the start to the end city, or the string "No path exists" if there is no possible route.

## sample

4
0 3 -1 7
8 0 2 -1
5 -1 0 1
2 -1 -1 0
0 3

6