Змішані плани польотів

Ad Hoc Поштова Компанія (AHPC) використовує просту стратегію доставки поштових конвертів: вона залучає волонтера, купує для нього найдешевший авіаквиток з початкового до кінцевого міста і передає йому сумку з конвертами в аеропорту відправлення, щоб він передав її кореспонденту компанії в аеропорту призначення.

Окрім прямих рейсів між двома аеропортами, існують непрямі маршрути з зупинками в кількох проміжних аеропортах. Пасажир непрямого маршруту завжди починає з першого аеропорту і відвідує проміжні аеропорти послідовно (згідно з розкладом непрямого маршруту, без використання інших прямих рейсів або непрямих маршрутів посередині), але може завершити маршрут в будь-якому проміжному аеропорту. Вартість непрямого маршруту фіксована; незалежно від того, чи пасажир використовує всі рейси або перериває маршрут посередині. План польоту може включати кілька прямих рейсів і повних або часткових непрямих маршрутів.

З метою економії, AHPC прагне використовувати комбіновані плани польотів: припустимо, що є пара сумок, одну потрібно доставити з $A$ до $B$, а іншу з $C$ до $D$ ($A$, $B$, $C$, $D$ — різні аеропорти). Компанія може купити два плани польотів з $A$ до $D$ для першого волонтера і з $C$ до $B$ для другого, так що обидва плани мають спільний аеропорт $M$ (не обов'язково відмінний від цих $4$ аеропортів), де волонтери зустрічаються і обмінюються сумками. Таким чином, AHPC гарантує, що кожна сумка доставлена до правильного місця призначення, при цьому загальна вартість може бути знижена.

Як приклад, шість аеропортів разом з прямими рейсами (суцільні стрілки), непрямими маршрутами (штрихові та крапкові стрілки) і їхніми цінами показані на наведеній вище схемі. Дві сумки повинні бути відправлені, одна з аеропорту $3$ ($A$) до $5$ ($B$), інша з $6$ ($C$) до $1$ ($D$). Компанія може придбати $(3,4)$, $(4,5)$ як план польоту для першого волонтера, і $(6,5)$, $(5,1)$ для другого із загальною вартістю $300$. Але дешевшою альтернативою буде (3, 4, 1, 2, 6) для першого і $(6,2)$, (2, 4, 5) для другого волонтера, із загальною вартістю $250$. Волонтери зустрічаються і обмінюються сумками в аеропорту $4$ ($M$), а перший волонтер залишить непрямий маршрут в аеропорту $1$.

Вам потрібно написати програму, яка, отримавши інформацію про рейси, знаходить найбільш економічну вартість доставки сумок.