Obyvateľov Absurdistanu už omrzelo, že ich krajinu tvorí len púšť. Prišli preto prosiť veľkého vezíra, aby dal postaviť diaľnice medzi mestami.
Veľký vezír si dal pre každé dve mestá zistiť cenu postavenia diaľnice medzi nimi. S prekvapením zistil, že táto cena je občas aj záporná — obyvatelia miest sú na diaľnicu ochotní prispieť viac ako v skutočnosti stojí postaviť ju.
Projektanti v Absurdistane zatiaľ neprišli na to, ako spraviť z diaľnice exit, preto sa na diaľnicu a z diaľnice dá dostať len v jej koncových mestách. Ak by sa nejaké diaľnice mali križovať, vyrieši sa toto kríženie mimoúrovňovo, pričom cenu ich stavby to neovplyvní.
Nájdite najlacnejší spôsob, ako postaviť diaľnice tak, aby sa po nich z každého mesta dalo dostať do každého iného. Medzi každými dvomi mestami smiete samozrejme postaviť najviac jednu priamu diaľnicu.
V prvom riadku vstupu je počet miest v Absurdistane $N$ $(1\leq N\leq 1000)$.
Nasleduje $N$ riadkov a v každom $N$ celých čísel; $j$-te číslo v $i$-tom riadku je cena $a_{i,j}$ postavenia diaľnice medzi $i$-tym a $j$-tym mestom. Pre všetky $i$, $j$ platí, že $|a_{i,j}|\leq 100\,000$, $a_{i,j} = a_{j,i}$ a $a_{i,i} = 0$.
Vypíšte jeden riadok a v ňom jedno celé číslo: najlacnejšiu celkovú cenu postavenia diaľnic (môže byť aj záporná).
5
0 -100 100 100 100
-100 0 10 15 10
100 10 0 10 100
100 15 10 0 100
100 10 100 100 0
-70
Postaviť treba diaľnice 1-2, 2-3, 3-4 a 2-5, celková cena bude $(-100)+10+10+10 = (-70)$.