Gəzinti

Olimpiya nəqliyyat sistemində islahatlar aparıldıqdan sonra, bu ölkə gözəl şəhərləri və hamar yolları ilə çiçəklənən bir məkana çevrildi. Hər yolun öz gözəlliyi var və bu gözəllik üçün müəyyən bir qiymət ödəmək lazımdır. Keçdiyiniz yolun qiyməti, həmin yoldakı yolların gözəlliklərinin ən böyüyünə bərabərdir. Məsələn, əgər siz [3, 1, 6, 4, 5] gözəlliklərə malik yollardan keçmisinizsə, bu yol üçün 6 sikkə ödəməlisiniz. Hər bir şəhər j öz tipinə malikdir T[j], və tiplər təkrarlana bilər.

İndi ölkənin turizm sistemində islahatlar aparmaq lazımdır. Hakimiyyət q turistik marşrut açmağı planlaşdırır və bu marşrutlar x[i] şəhərindən başlayıb y[i] şəhərində bitir. Hər marşrut i ən azı k[i] fərqli tipli şəhərlərdən keçməlidir.

Qeyd etmək lazımdır ki, əgər biz f sikkə ödəmişiksə, istədiyimiz qədər bu qiymətə və ya daha aşağı qiymətə malik yollardan keçə bilərik. Buna görə də yol sadə olmaya və döngələr ehtiva edə bilər.

Siz əvvəlki islahatlarda özünüzü yaxşı göstərdiyiniz üçün hakimiyyət yenidən sizin köməyinizə müraciət edir. Hakimiyyət tərəfindən verilmiş marşrutlar üçün minimal mümkün qiyməti tapın. Siz hansı şəhərləri ziyarət edəcəyinizi və hansı yollardan keçəcəyinizi özünüz qərar verə bilərsiniz, əsas odur ki, yol x[i] şəhərində başlayıb y[i] şəhərində bitsin və ən azı k[i] fərqli tipli şəhərlərdən keçsin.

Giriş Məlumatları

Birinci sətirdə ölkədəki şəhərlərin və yolların sayını göstərən üç ədəd N, M və Q var.

İkinci sətirdə N ədəd var, j-ci ədəd j-ci şəhərin tipini T[j] göstərir.

Növbəti M sətirdə yolların təsviri var. Hər sətirdə 3 ədəd a[j], b[j], c[j] var, yol a[j] və b[j] şəhərlərini birləşdirir və gözəlliyi c[j]-dir.

Növbəti q sətirdə marşrutların təsviri var, hər marşrut 3 ədəd x[i], y[i], k[i] ilə verilir, şərtdə təsvir edildiyi kimi.

1 ≤ T[j] ≤ 10^51 ≤ c[j] ≤ 10^51 ≤ a[j], b[j], x[i], y[i] ≤ N2 ≤ k[i] ≤ N1 ≤ q ≤ 10^4

Çıxış Məlumatları

q ədəd çıxarın, hər biri bir sətirdə. i-ci sətirdəki ədəd i-ci marşrut üçün minimal mümkün qiymətdir. Əgər belə bir marşrut mümkün deyilsə, -1 çıxarın.

Nümunələr

Qiymətləndirmə

25 bal 2 ≤ N,M,Q ≤ 100, k[i] = 2

35 bal 2 ≤ N,M,Q ≤ 100

40 bal 2 ≤ N,M ≤ 10^5

İzah

Birinci testin birinci marşrutunda 3 → 2 → 1 → 2 → 3 → 4 yolundan keçmək lazımdır, bu halda biz [3; 5; 5; 3; 2] gözəlliklərə malik yollardan keçəcəyik, yəni yolun qiyməti 5 olacaq.