17 стільців#4257
Остап Бендер знову намагається роздобути цінні коштовності, але цього разу вони заховані у спеціальній скриньці, яку можна відкрити лише ключами. Випадково кожен ключ заховано в одному з стільців, які були продані на нещодавньому аукціоні. Після аукціону ці стільці доставили у різних міст.
Тепер Остап вирішив відвідати кожне з міст, щоб ретельно обшукати їх та зібрати всі ключі зі стільців. Щоб уникнути зайвих ускладнень, Остап не хоче відвідувати жодне місто більше одного разу. Також у нього є список вартостей поїздок між кожною парою міст. Початково Остап знаходиться у місті номер , і після збору всіх ключів, відвідавши кожне місто, він спокійно може залишити країну.
Допоможіть Остапу визначити порядок відвідувань міст таким чином, щоб витратити якнайменше грошей на подорожі. Можливо, якщо у вас вийде, він поділиться з вами часткою знайдених коштовностей.
У першому рядку знаходиться кількість міст .
Далі йдуть рядків по невід'ємних цілих чисел у кожному. -те число у -му рядку вказує на вартість поїздки з міста до міста . Якщо a_{ij} > 0, то вартість дорівнює a_{ij} рублів; у іншому випадку, це означає, що прямий переїзд з міста до міста неможливий.
Кількість міст не перевищує кількості, зазначеної у назві задачі, а вартість поїздки між двома містами не перевищує .
У першому рядку виведіть мінімальну суму грошей, необхідну Остапу, щоб відвідати всі міста. У наступному рядку виведіть чисел — порядок, у якому Остап має відвідати міста для досягнення цієї вартості.
Якщо неможливо зібрати всі ключі, дотримуючись зазначених умов, виведіть одне число .
Приклад 1
Приклад 2