Экскалибур

Ekskalibur, əfsanəvi Kral Arturun qılıncı, bəzən sehrli güclərə malik olduğu və ya Britaniyanın qanuni hakimiyyəti ilə əlaqəli olduğu düşünülür. Alan, Böyük Britaniyanın kralı olmaq üçün Ekskaliburu yaratmağa qərar verir. Bunun üçün sizə qılınc yaratmağa imkan verən qədim bir sehr təqdim olunur. Sehrli tilsimdə m söz var və hər biri müəyyən bir tam ədəd w[i] ilə təmsil olunur. Tilsimi tətbiq etmək üçün n zirvələri və m kənarları olan, döngəsiz və çoxkənarsız əlaqəli bir qraf qurmalısınız. Kənarların çəkiləri sehrli tilsimdən olan çəkilər olmalıdır. Yəni, bu qrafın çəkiləri w[i] ardıcıllığının bir permutasiyasını təşkil etməlidir. Bu qrafda minimal skelet ağacının kənarlarının cəmi X-ə bərabər olmalıdır. Minimal skelet ağacı, n - 1 kənarı olan, döngəsiz, əlaqəli, yönsüz qrafdır ki, burada kənarların cəmi mümkün olan ən kiçikdir.

Giriş Məlumatları

Birinci sətir 3 tam ədəd n, m, X (2 ≤ n ≤ 100, 0 ≤ m ≤ 1000, 0 ≤ X ≤ 4000) ehtiva edir. İkinci sətir m tam ədəd w[i] (1 ≤ w[i] ≤ 40) ehtiva edir.

Çıxış Məlumatları

Əgər Ekskaliburu yaratmaq mümkün deyilsə, -1 çıxarın. Əks halda, birinci sətirdə m çıxarın. Növbəti m sətirdə hər biri 3 tam ədəd u, v, c (1 ≤ u ≤ n, 1 ≤ v ≤ n, u ≠ v, 1 ≤ c ≤ 40) - qrafın kənarlarını çıxarın. Kənarların çəkiləri giriş ardıcıllığı w[i]-in bir permutasiyasını təşkil etməlidir.