Tacirin üç növ malı var: almaslar, almalar və ipək. Hər malın vahid çəkisinin qızıl pulla qiyməti və tacirdə onun miqdarı məlumdur. Tacirin yaşadığı ölkədə \textbf{1-}dən\textbf{ N}-dək nömrələnmiş \textbf{N} şəhər var. Tacirin döğma şəhərinin nömrəsi \textbf{1}, paytaxtın nömrəsi isə \textbf{N}-dir. Tacirin mallarını satmalı olduğu paytaxta getməsi üçün onun digər şəhərlərdən keçən müəyyən marşrutla keçməsi lazımdır. Bəzi şəhərlər cütü arasında qatar bileti müəyyən sayda qızıla bərabər olan yol var. Hər şəhərdə oradan keçən hər mal üçün qiymətinin müəyyən faizi qədər vergi tutulur. Məlumdur ki, ixtiyari bir şəhərdən çıxan tacir oraya bir də qayıda bilməz. İxtiyari iki şəhər ən çoxu bir yol ilə birləşdirilmişdir. Tacirin məqsədi ən çox qazanc - paytaxtda satdığı maldan aldığı pul ilə paytaxta gələnədək sərf etdiyi pulun fərqi-əldə etməkdir. O mallarının hamısını özü ilə götürməyə məcbur deyil. Tacirin vergiləri ödəmək üçün həmişə kifayət qədər qızılı var və paytaxta satmağa apardığı mallarla hesablaşma apara bilməz. Bütün yollar yalnız bir istiqamətə aparır. Tacirdə olan hər bir növ malın çəkisi, bu malların paytaxtda qiyməti, şəhərlərdəki vergilər, şəhərlər arasındakı yollar və bu yollar üzrə gediş qiyməti haqqında informasiya əsasında malların satışından tacirin ala biləcəyi ən çox qazancı müəyyənləşdirmək üçün proqram yazın. \InputFile Giriş faylının birinci sətrində iki tam\textbf{ N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{500}) və \textbf{M} (\textbf{M} ≥ \textbf{1}) ədədləri-şəhərlərin və onlar arasındakı yolların sayı yerləşir. İkinci sətirdə tacirə məxsus almaz, alma və ipəyin ölçü vahidləri ilə miqdarını göstərən üç mənfi olmayan tam ədəd yerləşir. Üçüncü sətirdə uyğun olaraq almaz, alma və ipəyin bir ölçü vahidi çəkisinin qiymətləri olan üç mənfi olmayan tam ədəd yerləşir. Sonrakı \textbf{4}-cüdən \textbf{N+1}-dək sətrin hər birində \textbf{0}-dan \textbf{100}-dək (100 də daxil olmaqla) üç tam ədəd - uyğun olaraq almaz, alma və ipəyin qiymətlərinin \textbf{2}-ci şəhərdən \textbf{N-1} şəhərə kimi vergi kimi tutulan faizləri yerləşir. Şəhərlərin siyahısında onlarda tacirdən vergi alınmadığına görə tacirin doğma \textbf{1} nömrəli şəhəri və \textbf{N} nömrəli paytaxt nəzərə alınmamışdır. Sonrakı \textbf{M} sayda sətirdə üç mənfi olmayan tam ədəd - onlardan birinci ikisi aralarında yol olan \textbf{1-}dən\textbf{ N-}dək şəhərlər cütünü göstərir, digəri isə bu yol üzrə gediş haqqını bildirir. Yollar nömrəsi birinci göstərilmiş şəhərdən ikinci göstərilən şəhərə qədər aparır. Tacirdə olan hər növ malın ölçü vahidi ilə miqdarı, malların qiymətləri və yollar üzrə gediş haqqı \textbf{100-}ü aşmır. \OutputFile Çıxış faylının yeganə sətrində bir ədəd - paytaxta səfər zamanı əldə edilən ən çox qazancın tapılmış dəqiq qiyməti yerləşməlidir. Cavab həmişə vergüldən sağda düz iki rəqəm dəqiqliyi ilə verilməlidir. Tacirin qazanc əldə edə bilmədiyi və ya verilmiş yollarla paytaxta gedib çata bilmədiyi halda çıxışa \textbf{0.00} verilməsi tələb olunur.