ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ /8-р анги/

Штирлиц машинаар явж байв. Тэр машин зогсоохоор гараа өргөсөн Борманыг харсан боловч зогсолгүй явав. Штирлиц дахиад л гараа өргөсөн Борманыг харсан боловч зогссонгүй. Штирлиц Борманыг 3 дахь удаагаа харахад Борман : Намайг доромжилж байна даа гэж бодов.  Харин Штирлиц : Тойрог зам байна даа гэж бодов. Берлин хотод N тооны, хоорондоо замаар холбогдсон талбай байдаг. Штирлиц ням гарагийн өглөө босоод яг 3 талбайгаар дайран өнгөрдөг тойрог замыг сонгон уг замаараа машинаар зугаалах дуртай ажээ. Энэ үедээ Штирлиц Борманыг машин зогсоохоор гараа өргөн зогсч байна гэж төсөөлөх дуртай ба Штирлиц Борманыг аль болох олон удаа хархаыг хүсч байгаа. (Ингэснээр Штирлиц Борманыг илүү ихээр доромжилж таашаал авах нь ихэсдэг) Иймээс Штирлицийн явдаг замын нийт урт аль болох богино байх хэрэгтэй.

Input

Эхний мөрөнд талбайн тоо N байна. Дараагийн N тооны мөрөнд холболтын матрицыг өгнө. Үүнд гол диагоналиас бусад бүх элемент утгатай ба энэ утга нь хамгийн ихдээ 1000 байна. Гол диагоналийн бүх элемент 0 байна.

Output

Аль 3 талбайн хооронд явбал Штирлиц хамгийн их таашаал авахыг заасан 3 тоо байна

Example

Input:
5
0  20 10   30 40
20 0  30   1  2
10 30 0    40 1000
30 1  40   0  21
40 2  1000 21 0
Output: 4 5 2