Формула-1

У десятій державі є $n$ міст (1 \leq n \leq 800), пронумерованих від $1$ до $n$, та $m$ двосторонніх доріг (1 \leq m \leq 4000), які з'єднують ці міста. Команда "Ferrari" вирішила провести тестову сесію в цій державі. Вони планують провести $k$ заїздів (1 \leq k \leq 40) з першого міста до $n$-го так, щоб жоден заїзд не проходив по тій самій точній траєкторії, що й інший. За потреби, під час окремого заїзду дозволяється використовувати одну й ту саму дорогу кілька разів. Заїзд завершується, щойно водій досягає $n$-го міста (тобто, $n$-те місто не може бути проміжною точкою шляху). Щоб заощадити пальне, керівництво "Ferrari" вимагає, аби сумарна довжина маршрутів усіх заїздів була мінімальною. Знайдіть цю мінімальну сумарну довжину.