Qurd deşiklərinin sıralanması
Kəndli Conun inəkləri hər gün anbarı tərk etməzdən əvvəlki sıralamalardan beziblər. Onlar artıq kvant fizikası üzrə "elmlər doktoru" adını qazanıblar və bu prosesi sürətləndirməyə hazırdırlar.
Bu səhər, hər zamanki kimi, n inək, 1-dən n-ə qədər nömrələnmiş ardıcıl mövqelərdə, anbarın müxtəlif yerlərində yerləşir, belə ki, inək i mövqedə p[i] yerləşir. Lakin bu səhər m tunel ortaya çıxıb, 1-dən m-ə qədər nömrələnmiş, burada tunel i mövqeləri a[i] və b[i] iki tərəfli birləşdirir və eni w[i]-dir.
Hər hansı bir anda, tunelin əks uclarında yerləşən iki inək paralel olaraq mövqelərini dəyişə bilər. İnəklər bu şəkildə mövqelərini istədikləri qədər dəyişə bilərlər, ta ki, inək i mövqedə i olana qədər, 1 ≤ i ≤ n.
İnəklər tunellərdə əzilmək istəmirlər. Onlara ən kiçik enli tunelin enini maksimumlaşdırmağa kömək edin ki, onlar sıralana bilsinlər.
Giriş Məlumatları
Birinci sətir iki tam ədəd n (1 ≤ n ≤ 10^5) və m (1 ≤ m ≤ 10^5) ehtiva edir. İkinci sətir n tam ədəd p[1], p[2],..., p[n] ehtiva edir. Zəmanət verilir ki, p 1-dən n-ə qədər olan rəqəmlərin permutasiyasıdır.
Hər bir i üçün, 1 və m arasında, i + 2 sətiri tam ədədlər a[i], b[i] və w[i] (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i], 1 ≤ w[i] ≤ 10^9) ehtiva edir.
Çıxış Məlumatları
Bir tam ədəd çıxarın - inəklərin sıralanması zamanı istifadə etməli olduqları ən kiçik enli tunelin ən böyük enini. Əgər inəklər sıralanma zamanı tunelləri istifadə etmirlərsə, -1 çıxarın.
Nümunə
İnəkləri sıralamaq üçün yalnız bir variant var, minimal eni 9 olan tunelləri istifadə edərək.
İnəklər 1 və 2 üçüncü tuneli istifadə edərək mövqelərini dəyişirlər.
İnəklər 1 və 3 birinci tuneli istifadə edərək mövqelərini dəyişirlər.
İnəklər 2 və 3 üçüncü tuneli istifadə edərək mövqelərini dəyişirlər.