Миша живет в стране, в которой есть $$$n$$$ городов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Он живет в городе $$$1$$$.

Между каждой парой городов ходит поезд. Назовем маршрутом проезд по поезду из города $$$i$$$ в город $$$j$$$, где $$$i \neq j$$$. В частности, всего есть $$$n(n-1)$$$ разных маршрутов. У каждого маршрута есть своя стоимость, и стоимость маршрута из города $$$i$$$ в город $$$j$$$ может отличаться от стоимости маршрута из города $$$j$$$ в город $$$i$$$.

Миша хочет начать в городе $$$1$$$, совершить ровно $$$k$$$ переездов из одного города в другой, и в конце снова оказаться в городе $$$1$$$. Миша — любитель экономить, так что он хочет, чтобы его путешествие было как можно более дешевым. Обратите внимание, что Миша может посещать один город и даже проезжать по одному маршруту несколько раз.

Миша считает, что путешествие удалось, если среди маршрутов, которые он использовал в своем путешествии, нельзя найти нечетный цикл. Иначе говоря, если можно начать в каком-то городе $$$v$$$, который посетил Миша, проехать по нечетному числу маршрутов, которые использовал Миша, вернувшись в город $$$v$$$, то путешествие считается неудачным.

Ваша задача помочь Мише, и найти самое дешевое (с минимальной суммой стоимостей маршрутов на нем) путешествие, которое Миша будет считать удачным.