PROGRAMMING:Grand Line
"I'm the man who wants to be the pirate king!", While shouting such slogans, Luffy embarked on the arduous journey of the great route with his friends.
Luffy's great route starts at Rogge town and ends at lourderu (one piece is the only secret hidden there). In the middle of the voyage, there are all kinds of islands.
Because the climate on the great route is very abnormal, the time between any two islands varies greatly. It may take $$1 $$days from $$a $$island to $$B $$Island, and it may take $$1 $$years from $$B $$island to $$a $$island. Of course, the sailing time between any two islands is known, though it varies greatly.
Now suppose Luffy and his party set out from Rogge town (the starting point), traversed all the islands in the middle of the great route (but the passed islands can't be passed again), and finally arrived at dalafdru (the ending point). If they don't make any stops on the island, how long does it take them to reach the destination?
###Input format:
The first line contains an integer $$n $, which represents a total of $$n $$islands on the great route (including Rogge town at the beginning and lourderu at the end). The starting point is numbered $$1 $, and the ending point is numbered $$n $.
Each of the following n rows contains $$n $$integers, where the $$J (1 / Le J / Le n) $$integer in the $$I (1 / Le I / Le n) $$row represents the time from the $$I $$island to the $$J $$island. The $$I $$integer in line $$I $$is $$0 $.
###Output format:
The output is an integer representing the minimum time required for Luffy to reach the destination after traversing all intermediate islands from the starting point.
###Input sample 1:
```in
four
0 10 20 999
5 0 90 30
99 50 0 10
999 1 2 0
```
###Output sample 1:
```out
one hundred
```
###Explanation of example 1
Luffy starts from the starting island of $$1 $, passes through island of $$3 $, island of $$2 $, and finally arrives at Destination Island of $$4 $. The time spent is $$20 + 50 + 30 = 100 $$.
###Input sample 2:
```in
five
0 18 13 98 8
89 0 45 78 43
22 38 0 96 12
68 19 29 0 52
95 83 21 24 0
```
###Output sample 2:
```out
one hundred and thirty-seven
```
###Explanation of example 2
For the example, enter $$2 $: the possible path and total time are:
$$1,2,3,4,5: 18+45+96+52=211$$
$$1,2,4,3,5: 18+78+29+12=137$$
$$1,3,2,4,5: 13+38+78+52=181$$
$$1,3,4,2,5: 13+96+19+43=171$$
$$1,4,2,3,5: 98+19+45+12=174$$
$$1,4,3,2,5: 98+29+38+43=208$$
So the shortest time cost is $$137$$
###Data scale and agreement
For all $$n $$, there is $$2 < n / Le 16 $$; For all $$t $$, there is $$0 < T < 10000 $$.
answer：If there is no answer, please comment
Luffy's great route starts at Rogge town and ends at lourderu (one piece is the only secret hidden there). In the middle of the voyage, there are all kinds of islands.
Because the climate on the great route is very abnormal, the time between any two islands varies greatly. It may take $$1 $$days from $$a $$island to $$B $$Island, and it may take $$1 $$years from $$B $$island to $$a $$island. Of course, the sailing time between any two islands is known, though it varies greatly.
Now suppose Luffy and his party set out from Rogge town (the starting point), traversed all the islands in the middle of the great route (but the passed islands can't be passed again), and finally arrived at dalafdru (the ending point). If they don't make any stops on the island, how long does it take them to reach the destination?
###Input format:
The first line contains an integer $$n $, which represents a total of $$n $$islands on the great route (including Rogge town at the beginning and lourderu at the end). The starting point is numbered $$1 $, and the ending point is numbered $$n $.
Each of the following n rows contains $$n $$integers, where the $$J (1 / Le J / Le n) $$integer in the $$I (1 / Le I / Le n) $$row represents the time from the $$I $$island to the $$J $$island. The $$I $$integer in line $$I $$is $$0 $.
###Output format:
The output is an integer representing the minimum time required for Luffy to reach the destination after traversing all intermediate islands from the starting point.
###Input sample 1:
```in
four
0 10 20 999
5 0 90 30
99 50 0 10
999 1 2 0
```
###Output sample 1:
```out
one hundred
```
###Explanation of example 1
Luffy starts from the starting island of $$1 $, passes through island of $$3 $, island of $$2 $, and finally arrives at Destination Island of $$4 $. The time spent is $$20 + 50 + 30 = 100 $$.
###Input sample 2:
```in
five
0 18 13 98 8
89 0 45 78 43
22 38 0 96 12
68 19 29 0 52
95 83 21 24 0
```
###Output sample 2:
```out
one hundred and thirty-seven
```
###Explanation of example 2
For the example, enter $$2 $: the possible path and total time are:
$$1,2,3,4,5: 18+45+96+52=211$$
$$1,2,4,3,5: 18+78+29+12=137$$
$$1,3,2,4,5: 13+38+78+52=181$$
$$1,3,4,2,5: 13+96+19+43=171$$
$$1,4,2,3,5: 98+19+45+12=174$$
$$1,4,3,2,5: 98+29+38+43=208$$
So the shortest time cost is $$137$$
###Data scale and agreement
For all $$n $$, there is $$2 < n / Le 16 $$; For all $$t $$, there is $$0 < T < 10000 $$.
answer：If there is no answer, please comment