Маршрутизація корів (Срібло)

Втомившись від холодної зимової погоди на своїй фермі, корова Бессі планує вирушити у відпустку до тепліших країв. На жаль, вона виявляє, що лише одна авіакомпанія, Air Bovinia, готова продавати квитки коровам, причому ці квитки влаштовані досить складно.

Air Bovinia володіє $n$ літаками, кожен з яких літає за певним «маршрутом», що складається з двох або більше міст. Наприклад, один із літаків може летіти за маршрутом, який починається в місті $1$, потім проходить через місто $5$, потім через місто $2$ і, нарешті, прибуває в місто $8$. Жодне місто не зустрічається в одному маршруті більше одного разу.

Якщо Бессі вирішує скористатися маршрутом, вона може сісти в літак у будь-якому місті цього маршруту, а потім вийти в будь-якому місті, яке розташоване пізніше по маршруту. Їй не обов'язково сідати в першому місті маршруту або виходити в останньому. Кожен маршрут має фіксовану вартість, яку Бессі повинна сплатити при кожному використанні будь-якої частини цього маршруту, незалежно від кількості міст, через які вона проїде.

Якщо Бессі використовує один і той самий маршрут кілька разів під час своєї подорожі (тобто залишає маршрут, а потім пізніше повертається до нього і знову використовує його, починаючи з іншого міста), вона повинна платити вартість цього маршруту кожного разу.

Бессі хоче знайти найдешевший спосіб дістатися від своєї ферми, розташованої в місті $A$, до свого тропічного місця призначення, розташованого в місті $B$. Допоможіть їй визначити як мінімальну загальну вартість подорожі, так і, серед усіх маршрутів з такою мінімальною вартістю, мінімальну кількість окремих перельотів, яку їй необхідно здійснити.