Миша живет в стране, в которой есть \(n\) городов, пронумерованных целыми числами от \(1\) до \(n\). Он живет в городе \(1\).
Между каждой парой городов ходит поезд. Назовем маршрутом проезд по поезду из города \(i\) в город \(j\), где \(i \neq j\). В частности, всего есть \(n(n-1)\) разных маршрутов. У каждого маршрута есть своя стоимость, и стоимость маршрута из города \(i\) в город \(j\) может отличаться от стоимости маршрута из города \(j\) в город \(i\).
Миша хочет начать в городе \(1\), совершить ровно \(k\) переездов из одного города в другой, и в конце снова оказаться в городе \(1\). Миша — любитель экономить, так что он хочет, чтобы его путешествие было как можно более дешевым. Обратите внимание, что Миша может посещать один город и даже проезжать по одному маршруту несколько раз.
Миша считает, что путешествие удалось, если среди маршрутов, которые он использовал в своем путешествии, нельзя найти нечетный цикл. Иначе говоря, если можно начать в каком-то городе \(v\), который посетил Миша, проехать по нечетному числу маршрутов, которые использовал Миша, вернувшись в город \(v\), то путешествие считается неудачным.
Ваша задача помочь Мише, и найти самое дешевое (с минимальной суммой стоимостей маршрутов на нем) путешествие, которое Миша будет считать удачным.