Stasionar telefon şəbəkəsi#7531
Şəhər RMR-in meri şəhər xarici dünya ilə əlaqəsi kəsildiyi fövqəladə hallarda istifadə ediləcək təhlükəsiz telefon şəbəkəsi yaratmaq istəyir. Şəhərdəki bəzi binalar cütlükləri birbaşa telefon xətti ilə birləşdirilə bilər. Bələdiyyə mühəndisləri hər belə cütlük üçün birləşmə xərcinin qiymətləndirilməsini hazırlayıblar.
Merin köməyinizə ehtiyacı var: təhlükəsizlik tələblərinə uyğun olaraq şəhərdəki bütün binaları birləşdirən ən ucuz şəbəkəni qurmaq lazımdır. Binadan binaya zəng sadə yol ilə həyata keçirilməlidir (yəni təkrarlanan binaları olmayan yol ilə). Bütün binalar arasında cinayət keçmişi olan insanların yaşadığı bir neçə təhlükəli bina var. Mer bu binalara yalnız şəbəkədən giriş olmasını, əksini deyil, istəyir. Başqa sözlə, binalar və arasında heç bir əlaqə təhlükəsiz olmayan bina -dən keçməməlidir (burada və -dən fərqlidir).
Birinci sətir üç tam ədəd n, m, p ehtiva edir, burada n~(1 \le n \le 1000) — bina sayı, m~(0 \le m \le 10^5) — binalar cütlükləri arasında mümkün olan birbaşa əlaqələrin sayı və p~(0 \le p \le n) — təhlükəsiz olmayan bina sayı. Binalar -dən -ə qədər nömrələnib.
İkinci sətir müxtəlif tam ədəd ehtiva edir, hər biri -dən -ə daxil — təhlükəsiz olmayan binaların nömrələri.
Sonrakı sətirin hər birində üç tam ədəd x_i, y_i və l_i var, onlar bir potensial birbaşa əlaqəni təsvir edir: x_i və y_i~(1 \le x_i, y_i \le n) — birləşdirilən binaların fərqli nömrələri və l_i~(1 \le l_i \le 10000) — belə bir birləşmənin dəyəri.
Hər hansı iki bina cütü arasında birbaşa bir əlaqə mövcuddur.
Əgər mümkünsə, təhlükəsizlik şərtlərinə cavab verən ən ucuz şəbəkənin dəyərini yazdırın. Belə bir şəbəkənin qurulması mümkün deyilsə, "impossible" yazdırın.
Nümunə 1
Nümunə 2