Остап Бендер знову пробує отримати належні йому коштовності, але у цей раз вони були закриті у шкатулці для відкирття якої необхідно мати n ключів. За закономірною випадковістю кожен з ключів було сховано у одному з n стільців, розпроданих на нещодавньому аукціоні. Після аукціону ці стільці були розвезені у n міст.

І ось тепер Остап рішився на нову безумну ідею: заїхати у кожне з міст і, провернувши у кожному з них аферу, викрасти необхідні ключі. Щоб уникнути конфліктов з недоброзичливцями Остап не хоче більше одного разу появлятись у якому-небудь місті. Також у Остапа є список цін за проїзд між кожною парою міст. Спочатку Остап знаходиться у місті під номером 1 і після відвідування усіх міст може непомітно виїхати з цієї країни.

Допоможіть Остапу знайти такий порядок відвідування міст при якому йому потрібно буде витратити якомога менше коштів на подорожі і тоді, можливо, він поділиться з Вами добутими діамантами.

Вхідні дані

Перший рядок містить єдине число n - кількість міст.

Наступні n рядків містять по n цілих невід'ємних чисел. j-те число в i-тому рядку позначає вартість проїзду з міста i у місто j. Якщо aij > 0, то проїзд коштує aij рублів, інакше - це означає, що з міста i в j номожливо проїхати напряму.

Кількість міст не перевищує числа, згадуваного в умові задачі, а вартість проїзду між двома містами не перевищує 100.

Вихідні дані

У першому рядку виведіть мінімальну суму грошей, необхіну для відвідування усіх міст Остапом. У наступному рядку виведіть n чисел - порядок відвідування міст, при якому ця сума досягається.

Якщо дістати усі ключі Остапу не вдасться з дотриманням вказаних в умові задач умов - виведіть єдине число -1.