Məsafə
Böyük şəhərdə mobil operator "piyadanın naviqasiyası" adlı öz yeni xidmətini genişləndirmək üçün abonentlər arasında müsabiqə keçirir. Əsas mükafat bir-biri ilə görüşəcək ilk cütlüyə təqdim ediləcək.
Müsabiqənin əvvəlində bütün abonentlər öz mövqelərində olurlar. Məlumdur ki, onlar bir-birini öz smartfonlarında görə bilirlər və yalnız piyada yol ilə 10 km/saat sabit sürətlə hərəkət edirlər.
Mobil operator mükafatlandırma mərasiminə hazırlaşmaq üçün müsabiqənin bitməsindən sonra ən az zamanı bilməlidir.
Giriş verilənləri
İlk sətir üç N, K və L tam ədədlərini - mobil operatordakı abonentlərin sayını (2 ≤ N ≤ 10^5), qovşaqların sayını (1 ≤ K ≤ 10^5) və şəhərdə piyada gəzmə saylarını (1 ≤ L ≤ 10^5) ehtiva edir.
Növbəti N sətirdə abonentlərin başlanğıc mövqelərini ifadə edən S_i (1 ≤ S_i ≤ K) ədədləri (transport qrafının qovşaqları)
Növbəti L sətirdə piyadaların gedişlərini əks etdirən boşluqla ayrılmış B_i, C_i və D_i tam ədədləri verilir. Hər bir sətir ona işarə edir ki, B_i və C_i (1 ≤ B_i, C_i ≤ K, B_i ≠ C_i) qovşaqları arasında uzunluğu D_i (1 ≤ D_i ≤ 5000) kilometr olan ikiistiqamətli yol mövcuddur.
Çıxış verilənləri
Müsabiqənin bitməsi üçün mümkün minimal dəqiqələrin sayını verin. Ən az bir cüt abonentin görüşəcəyinə təminat verilir.