Telefon xətləri
Fermer Con öz fermasında telefon xəttini quraşdırmaq istəyir. Təəssüf ki, telefon şirkəti bu işdə kömək etmir, buna görə də Con fermasını telefon şəbəkəsinə qoşmaq üçün bəzi kabellərin pulunu ödəməlidir.
Fərmer Conun mülkü ətrafında n tərk edilmiş telefon dirəyi var, bunlar 1-dən n-ə qədər nömrələnib; heç bir kabel onları birləşdirmir. Ümumilikdə, p cüt dirəyi kabel vasitəsilə birləşdirmək mümkündür; qalanları isə bir-birindən çox uzaqdadır.
i-ci kabel iki fərqli dirəyi a[i] və b[i] uzunluğu l[i] (1 ≤ l[i] ≤ 10^6) ilə birləşdirə bilər, əgər istifadə olunarsa. Heç bir {a[i], b[i]} cütü bir dəfədən çox rast gəlinmir. Dirək 1 artıq telefon şəbəkəsinə qoşulub, dirək n isə fermada yerləşir. Dirəklər 1 və n kabellər vasitəsilə birləşdirilməlidir; digər dirəklər istifadə oluna bilər və ya olunmaya bilər.
Telefon şirkəti fermer Cona k ədəd kabel parçasını pulsuz təqdim etməyə hazırdır. Bundan əlavə, o, hələ də ehtiyac duyduğu kabellər arasında ən uzun kabelin uzunluğuna bərabər qiymət ödəməlidir (hər bir dirək cütü ayrı bir kabel ilə birləşdirilir) və ya əgər əlavə kabellərə ehtiyac yoxdursa, 0 ödəməlidir.
Fermer Conun ödəməli olduğu minimal məbləği müəyyən edin.
Giriş məlumatları
Birinci sətir üç tam ədəd n (1 ≤ n ≤ 1000), p (1 ≤ p ≤ 10000) və k (0 ≤ k < n) ehtiva edir. Növbəti p sətirin hər biri üç tam ədəd a[i], b[i] və l[i] ehtiva edir.
Çıxış məlumatları
Bir tam ədəd çıxarın - fermer Conun ödəyə biləcəyi minimal məbləğ. Əgər fermayı telefon şəbəkəsinə qoşmaq mümkün deyilsə, -1 çıxarın.