Telefon xətləri

Fermer Con öz fermasına telefon xətti çəkmək istəyir. Təəssüf ki, telefon şirkəti ona kömək etməyə o qədər də həvəsli deyil, buna görə də fermanı telefon şəbəkəsinə qoşmaq üçün lazım olan kabellərin bir hissəsini özü ödəməli olacaq.

Fermer Conun ərazisində $1$-dən $n$-ə qədər nömrələnmiş $n$ tənha telefon dirəyi səpələnmişdir. Hazırda onlardan heç biri kabellə digərinə birləşdirilməyib. Ümumilikdə kabellə birləşdirilə bilən $p$ dirək cütü var; qalan cütlər isə bir-birindən çox uzaqdır.

$i$-ci kabel iki fərqli dirəyi — a_i və b_i-ni birləşdirə bilər və uzunluğu l_i~(1 \le l_i \le 10^6) vahiddir. Hər bir {a_i,b_i} cütü giriş məlumatlarında ən çox bir dəfə rast gəlinir.

$1$ nömrəli dirək artıq telefon şəbəkəsinə qoşulub, $n$ nömrəli dirək isə fermada yerləşir. $1$ və $n$ dirəkləri kabellərdən ibarət bir yolla birləşdirilməlidir; qalan dirəklərdən istifadə edilə də bilər, edilməyə də bilər.

Telefon şirkəti fermer Cona pulsuz olaraq $k$ ədəd kabel parçası təqdim etməyə hazırdır. Bu $k$ pulsuz kabeldən artıq hər bir kabel üçün fermer ona lazım olan qalan kabellərin ən uzununun uzunluğuna bərabər məbləğ ödəməlidir, əlavə kabel lazım olmadıqda isə $0$ ödəyir.

Fermer Conun ödəməli olduğu minimum məbləği müəyyən edin.