Sehrli Zindan

"'markdown Artur C. Malory oyun dünyasında dolaşan cəsur bir döyüşçüdür.

Bir gün, kiçik bir kəndə gəldi və gecəni orada keçirdi. Ertəsi gün səhər, kəndin başçısı onu yanına çağırdı. Başçı dedi ki, bir canavar kəndi təhdid edir və ondan onu məğlub etməsini xahiş etdi. Artur, kəndi xilas etməyə qərar verdi.

Başçı ona bildirdi ki, canavar qərbdən gəlmiş kimi görünür. Beləliklə, Artur kəndin qərbindəki meşədən keçərək şübhəli bir mağara tapdı. Mağarada dərin bir zindan olduğunu gördü və bunun canavarın yuvası olduğuna əmin oldu.

Xoşbəxtlikdən, girişdə zindanın xəritəsini tapdı. Xəritəyə əsasən, canavar zindanın dərinliyində yaşayır. Zindanda bir çox otaq yollarla birləşir. Bütün yollar bir istiqamətlidir və sehrli güclə doludur. Sehrli güc, bir yoldan keçəndə onu sağaldır və ya zədələyir.

Ona dəyə biləcək zərərin miqdarı zərbə nöqtələri ilə göstərilir. O, əvvəlcə maksimal zərbə nöqtələrinə malikdir və bütün zərbə nöqtələrini itirərsə ölür. Təbii ki, ölü olan nə hərəkət edə bilər, nə də döyüşə bilər—onun ölümü missiyasının uğursuzluğu deməkdir. Digər tərəfdən, sağaldıcı yollardan keçərək zərbə nöqtələrini maksimal dərəcəyə qədər bərpa edə bilər. Sağaldığı və ya zədələndiyi miqdar xəritədə göstərilir.

İndi, o, canavarla ən yaxşı mümkün vəziyyətdə döyüşmək istəyir. Sizin işiniz onun canavarın otağına daxil olarkən zərbə nöqtələrini maksimuma çatdırmaqdır. O, oraya çatdıqda canavarla döyüşməlidir. Geri necə dönəcəyini düşünməyə ehtiyac yoxdur, çünki onun zindandan qaçmaq üçün sehrli bir parşömeni var.

Giriş verilənləri

Giriş bir neçə test halından ibarətdir.

Hər test halının ilk sətri iki tam ədəd N (2 ≤ N ≤ 100) və M (1 ≤ M ≤ 1000) ehtiva edir. N otaqların sayını, M yolların sayını göstərir. Otaqlar 0 -dan N−1 -ə qədər etiketlənmişdir. Növbəti M sətrin hər biri üç tam ədəd f_i, t_i və w_i (|w_i| ≤ 10^7) ehtiva edir ki, bu da otaqları birləşdirən bir yolu təsvir edir. f_i və t_i yolun giriş və çıxışını göstərir. w_i isə Arturun zərbə nöqtələrinə təsirini göstərir; w_i müsbət olarsa, zərbə nöqtələrini bərpa edir; əks halda itirir. Halın son sətri üç tam ədəd s, t və H (0 < H ≤ 10^7) ehtiva edir. s zindanın giriş otağını, t canavarın otağını və H Arturun maksimal zərbə nöqtələrini göstərir. s və t fərqli olduğunu, lakin f_i və t_i eyni ola biləcəyini qəbul edə bilərsiniz.

Son test halı iki sıfır ehtiva edən bir sətrlə bitir.

Çıxış verilənləri

Hər test halı üçün test halının nömrəsini (başlanğıcda 1 ilə) və Arturun canavarın otağında mümkün olan maksimum zərbə nöqtələrini ehtiva edən bir sətr çap edin. Əgər o, canavarla döyüşə bilmirsə, hal nömrəsini və "GAME OVER" yazısını çap edin. "'