Avtomobil Yolu Patrulu
Crimes Megacity şəhərində artmaqdadır. Cinayətlərlə mübarizə aparmaq üçün hakimiyyət orqanları bir magistral patrul yaratmışdır. Şəhər bir sıra tək istiqamətli yollardan ibarətdir. Hər yolun sonunda patrul qoşunları üçün bir baza stansiyası var. Hər bir baza stansiyasında bir neçə qoşun var. Əvvəlcə hər stansiya həmin stansiyadan çıxan bütün magistral yollara bir qoşun göndərir. Qoşun magistral yolu patrul edir və magistral yolun digər tərəfindəki stansiyaya çatdıqda orada gözləyir və orada ən çox gözləyən qoşun, ən uzun müddət patrul edilməmiş magistral yola göndərilir.
Tezliklə, bəzi çətinliklərlə üzləşdilər, çünki magistral yolun patrul edilmə tezliyi, getdikcə daha çox baza stansiyasında başlayan və bitən magistral yolların sayından asılı olur. Əgər bir baza stansiyasında başlayan magistral yolların sayı orada bitən magistral yolların sayından çoxdursa, yollar daha az tezliklə patrul edilir. Və əgər, bəzi baza stansiyasında heç bir magistral yol bitmirsə, oradan başlayan magistral yollar bir dəfədən çox patrul edilməyəcək.
Bu vəziyyətdə, magistral patrul bəzi magistral yolları patrul cədvəlindən çıxarmağa qərar verdi ki, hər baza stansiyasında başlayan və bitən magistral yolların sayı bərabər olsun. Qalan magistral yollar video müşahidə ilə izlənəcək. Amma, bəzi təhlükəsizlik məsələlərinə görə, bəzi magistral yollar patrul edilməlidir.
İndi, magistral yolların patrul edilmə xərci və video müşahidə quraşdırma xərci verildikdə, bütün şəhəri izləmək üçün minimum xərci tapın. Nəzərə alın ki, video müşahidə magistral patrulu tamamilə əvəz edə bilməz. Beləliklə, ən azı bir magistral yol patrul edilməlidir.
Giriş verilənləri
Girişin ilk sətri T (T ≤ 70), test halların sayını göstərən bir tam ədəddir. Bu, T test halları ilə davam edir. Hər test halı iki tam ədəd N (1 ≤ N ≤ 100) və M (1 ≤ M ≤ 1000), baza stansiyaların və magistral yolların sayını göstərir. Bu, M sətirlə davam edir, hər biri 5 tam ədəd, u, v, p, s, x (1 ≤ u, v ≤ N, 0 ≤ p, s ≤ 1000000) ehtiva edir, burada u və v baza stansiyasından başlayan və v baza stansiyasında bitən magistral yolu göstərir, p patrul xərci və s video müşahidə quraşdırma xərci göstərir. Əgər magistral yol patrul edilməlidirsə, x bir olacaq. Əks halda sıfır olacaq.
Çıxış verilənləri
Hər test halı üçün, hal nömrəsini və magistral yolları izləmək üçün minimum xərci çıxarın. Əgər verilmiş məhdudiyyətləri təmin edərək patrul etmək mümkün deyilsə, "impossible" (tırnaq işarələri olmadan) çıxarın.