Stirlitz was driving a car, saw Bormann voting, and drove past. After a while, he again saw Bormann voting, and again drove past. Soon he saw Bormann voting again.
- scoffs! thought Bormann.
- Ring! - Stirlitz guessed.
There are N squares in the city. Any two squares are connected to each other by exactly one two-way road. Stirlitz lives in this city. Stirlitz has a hobby - he likes to leave the house on Sunday mornings, get into the car, choose some ring route that passes exactly three squares (that is, first he goes from some square to some other, then to the third , then returns to the initial one, and again travels along this route). He imagines that Bormann is somewhere along the way. And so Stirlitz drives all Sunday, until his head is spinning, and rejoices...
Naturally, Stirlitz wants to drive past the point where, as he imagines, Bormann is standing, as often as possible. To do this, of course, the route chosen by Stirlitz should be as short as possible. Write a program that will choose the optimal route for Stirlitz.
Input
The first line specifies number N (3 <= N <= 100). The following lines contain a matrix of NxN distances between squares (the number in position i,j denotes the length of the road connecting the i-th and j-th squares). All numbers in the matrix (except for those on the main diagonal) are natural numbers, not exceeding 1000. The matrix is symmetrical with respect to the main diagonal, there are 0 on the main diagonal.
Imprint
It is required to print three numbers — numbers of areas in the optimal route. If there are several routes, print any of them.
Examples
| # |
Input |
Output |
| 1 |
5
0 1 9 9 2
1 0 9 9 9
9 9 0 9 9
9 9 9 0 9
2 9 9 9 0
| 1 2 5 |