Məsafə#1638
Böyük şəhərdə mobil operator abunəçiləri arasında yeni "piyadanın naviqasiyası" xidmətini təbliğ etmək üçün müsabiqə təşkil edir. Əsas mükafat bir-biri ilə ilk görüşən abunəçilər cütlüyünə veriləcək. Müsabiqə belə bir görüş baş verən kimi başa çatır.
Müsabiqənin əvvəlində bütün abunəçilər başlanğıc mövqelərdə olurlar. Məlumdur ki, onlar bir-birini smartfonlarında görə bilirlər və yalnız piyada yolları ilə sabit km/saat sürətlə hərəkət edirlər. Hər abunəçi mükafatı qazanmağa çalışır və digərlərinə laqeyddir.
Mükafatlandırma mərasimini təşkil etmək üçün operator müsabiqənin bitməsi üçün lazım olan minimal vaxtı bilməlidir.
İlk sətirdə üç tam ədəd , və verilir — abunəçilərin sayı (2 \leq N \leq 10^5), qovşaqların sayı (1 \leq K \leq 10^5) və şəhərdə piyada yollarının sayı (1 \leq L \leq 10^5).
Növbəti sətirdə hər abunəçinin başlanğıc mövqeyini göstərən bir tam ədəd S_i (1 \leq S_i \leq K) — (nəqliyyat qrafının qovşağı).
Daha sonra sətirdə hər birində boşluqla ayrılmış üç tam ədəd B_i, C_i və D_i verilir — B_i və C_i (1 \leq B_i, C_i \leq K, B_i \neq C_i) qovşaqları arasında uzunluğu D_i (1 \leq D_i \leq 5000) kilometr olan ikitərəfli piyada yolu mövcuddur.
Müsabiqənin başa çatması üçün keçə biləcək minimal mümkün dəqiqələrin sayını çıxışda göstərin.
Ən azı bir abunəçi cütünün görüşəcəyi təmin olunur.
Nümunə 1