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ə \textbf{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. \InputFile İlk sətir üç \textbf{N}, \textbf{K} və \textbf{L} tam ədədlərini - mobil operatordakı abonentlərin sayını (\textbf{2} ≤ \textbf{N} ≤ \textbf{10^5}), qovşaqların sayını (\textbf{1} ≤ \textbf{K} ≤ \textbf{10^5}) və şəhərdə piyada gəzmə saylarını (\textbf{1} ≤ \textbf{L} ≤ \textbf{10^5}) ehtiva edir. Növbəti \textbf{N} sətirdə abonentlərin başlanğıc mövqelərini ifadə edən \textbf{S_i} (\textbf{1} ≤ \textbf{S_i} ≤ \textbf{K}) ədədləri (transport qrafının qovşaqları) Növbəti \textbf{L} sətirdə piyadaların gedişlərini əks etdirən boşluqla ayrılmış \textbf{B_i}, \textbf{C_i} və \textbf{D_i} tam ədədləri verilir. Hər bir sətir ona işarə edir ki, \textbf{B_i} və \textbf{C_i} (\textbf{1} ≤ \textbf{B_i}, \textbf{C_i} ≤ \textbf{K}, \textbf{B_i} ≠ \textbf{C_i}) qovşaqları arasında uzunluğu \textbf{D_i} (\textbf{1} ≤ \textbf{D_i} ≤ \textbf{5000}) kilometr olan ikiistiqamətli yol mövcuddur. \OutputFile 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.