Formula-1
Otuzuncu dövlətdə n (1 ≤ n ≤ 800) şəhər var, bu şəhərlər 1-dən n-ə qədər nömrələnib və aralarında m (1 ≤ m ≤ 4000) ikitərəfli yollar mövcuddur. "Ferrari" komandası bu dövlətdə test sessiyası keçirməyə qərar verib. k (1 ≤ k ≤ 40) yarışın birinci şəhərdən n-ci şəhərə keçirilməsi planlaşdırılıb, lakin heç bir iki yarışın marşrutları tamamilə eyni olmamalıdır. Eyni yoldan bir neçə dəfə keçmək lazım gəldikdə, bəzi yarışlarda buna icazə verilir. Yarış, sürücü n-ci şəhərə çatdıqda başa çatır (yəni n-ci şəhər yarış marşrutunda aralıq nöqtə ola bilməz). Benzinə qənaət etmək məqsədilə "Ferrari" rəhbərləri tələb edirlər ki, bütün yarışların marşrutlarının ümumi uzunluğu ən az olsun. Sizdən bu uzunluğu tapmaq tələb olunur.
Giriş məlumatları
Birinci sətir k, n və m rəqəmlərini ehtiva edir. Sonra m üçlük rəqəmlər gəlir, yolları təsvir edir - yolla birləşdirilən şəhərlərin nömrələri və yolun uzunluğu (tam ədəd 1-dən 9500-ə qədər).
Çıxış məlumatları
Axtarılan ümumi uzunluğu çıxış edin. Bütün yarışların keçirilməsi üçün ən azı bir yolun mövcud olduğu təmin edilir.