Sehrli yollar
Sehrli bir ölkəyə düşmüsünüz. Bu ölkənin strukturu adi bir ölkə ilə eynidir: bir neçə şəhərdən ibarətdir və bəzi şəhərlər iki tərəfli yollarla birləşdirilib. Hər yolun öz uzunluğu var və sehrli təsadüflər nəticəsində bütün yolların uzunluqları fərqlidir.
Lakin adi krallıqlardan fərqli olaraq, sehrli ölkənin kralı istədiyini edə bilər. O, yolların tikilməsini əmr edə bilər və ya onları dağıda bilər. Lakin bu əmrlər artıq onu darıxdırıb... Son zamanlarda kral yeni bir oyun icad edib: o, bir fərman verdi ki, bir şəhərdən çıxan bütün yolların vəziyyəti əksinə çevrilsin. Hər yolun iki vəziyyəti var: ya istifadə olunur, ya da yox.
Siz krala yaxınlaşdınız. O, yaxşı əhval-ruhiyyədə idi və sizinlə oynamaq qərarına gəldi. Kral fərmanlar verdi və birdən sizə bir sual verdi. Əvvəlcə o, soruşmaq istədi: "sehrli ölkədəki bütün yollar arasında ən qısa yolun uzunluğu nədir?". Lakin tezliklə qərara gəldi ki, bu sadə bir sualdır. Və o, belə bir sual icad etdi: "Hal-hazırda istifadə olunan bütün yollar arasında k-cı ən qısa yolu tapın (əgər belə bir yol varsa)".
Çünki o, sehrli ölkənin kralı idi (günəş həmişə göy qurşağı sahələrinə işıq saçırdı), o, cavab səhv olarsa başınızı kəsmək qərarına gəldi. Buna görə də, bütün suallara düzgün cavab verməlisiniz.
Giriş məlumatları
Birinci sətir üç tam ədəd n, m və q (2 ≤ n ≤ 500, 1 ≤ m ≤ n * (n - 1) / 2, 1 ≤ q ≤ 200000) ehtiva edir: şəhərlərin sayı, yolların sayı və kralın sorğularının sayı. Növbəti m sətirin hər biri üç tam ədəd a[i], b[i] və c[i] (1 ≤ a[i], b[i] ≤ n, 1 ≤ c[i] ≤ 10^9) ehtiva edir: i-ci yol ilə birləşdirilən şəhərlərin nömrələri və yolun uzunluğu.
Hər hansı bir şəhər cütü arasında bir yoldan çox yol olmadığı və heç bir yolun özünə aparmadığı təmin edilir. Bütün yolların uzunluqları fərqlidir. Əvvəlcə bütün yollar istifadə olunur hesab edilir.
Növbəti q sətir kralın hərəkətlərini təsvir edir. Hər sətirdəki ilk ədəd x[i] hərəkətin növünü ehtiva edir. Əgər x[i] = 1, yeni fərman verilir. Sonra v[i] (1 ≤ v[i] ≤ n) - fərmanın verildiyi şəhərin nömrəsi gəlir. Əgər x[i] = 2, kral sizə sual verir. Bu halda, sonra tam ədəd k[i] (1 ≤ k[i] ≤ m) gəlir.
Çıxış məlumatları
Kralın hər sualına bir sətir çıxışda bir ədəd - suala cavab olmalıdır. Cavab hal-hazırda istifadə olunan yollar çoxluğundan k[i]-cı ən qısa yolun uzunluğu olmalıdır. Yollar girişdə verildiyi ardıcıllıqla nömrələnir. Əgər hər hansı bir anda k[i] qədər yol yoxdursa, k[i]-cı ən qısa yol sorğusuna -1 çıxış edin.