Formula-1

Onuncu ştatda $n$ şəhər (1 \leq n \leq 800), $1$-dən $n$-ə qədər nömrələnmiş, və bu şəhərləri birləşdirən $m$ ikitərəfli yol (1 \leq m \leq 4000) var. "Ferrari" komandası həmin ştatda test sessiyası keçirməyə qərar verib. Onlar birinci şəhərdən $n$-ci şəhərə doğru $k$ yarış keçirmək istəyirlər (1 \leq k \leq 40), elə ki, heç iki yarış tam olaraq eyni marşrutla getməsin. Əgər lazım gələrsə, bəzi yarışlarda eyni yoldan bir neçə dəfə istifadə oluna bilər. Yarış iştirakçısı $n$-ci şəhərə çatdığı anda yarış bitmiş sayılır (yəni, $n$-ci şəhər marşrutun ortasında yerləşə bilməz). Yanacağa qənaət etmək üçün "Ferrari" rəhbərliyi tələb edir ki, bütün yarışların marşrutlarının uzunluqlarının cəmi minimal olsun. Bu minimal cəmi tapın.