Shortest Path Between Warehouses

You are given an undirected weighted graph represented by an adjacency matrix, where the weight on an edge represents the distance between two warehouses. A value of 0 indicates that there is no direct connection between the warehouses. Given the number of warehouses, the adjacency matrix, a starting warehouse S, and a destination warehouse D, your task is to compute the shortest distance between S and D using Dijkstra's algorithm. If there is no valid route connecting the two warehouses, print -1.

The warehouses are numbered from 1 to n and the adjacency matrix is provided in a way such that the element in the i-th row and j-th column represents the distance from warehouse i to warehouse j.

Input Format: The input is read from standard input.

Output Format: Output the shortest path distance from warehouse S to warehouse D, or -1 if no such path exists.

Note: If there are multiple test cases, each test case should be processed individually.

inputFormat

The input begins with an integer n representing the number of warehouses. It is followed by n lines, each containing n space-separated integers denoting the adjacency matrix. Finally, there is a line with two space-separated integers: the starting warehouse S and the destination warehouse D.

Example:

4
0 10 15 0
10 0 0 20
15 0 0 30
0 20 30 0
1 4

outputFormat

Print a single integer representing the shortest distance from warehouse S to warehouse D. If there is no path, output -1.

## sample

4
0 10 15 0
10 0 0 20
15 0 0 30
0 20 30 0
1 4

30