Bilik labirinti
Yay Məktəb Kompüter Məktəbi (YMKM) "Bilik Labirinti" adlı bir attraksion təşkil edib. Bu labirint n otaqdan ibarətdir, otaqlar 1-dən n-ə qədər nömrələnib və bəzi otaqlar arasında qapılar mövcuddur. İnsan qapılardan keçdikdə, onun bilik göstəricisi həmin qapıya aid sabit bir dəyər qədər dəyişir. Labirintin girişi 1 nömrəli otaqda, çıxışı isə n nömrəli otaqdadır. Hər bir tələbə labirinti yalnız bir dəfə keçir və əldə etdiyi biliklərin miqdarına əsasən müəyyən bir təhsil qrupuna daxil olur (labirintə daxil olarkən bu göstərici sıfırdır). Sizin vəzifəniz ən yaxşı nəticəni göstərməkdir.
Giriş məlumatları
Birinci sətir n otaqların sayını (1 ≤ n ≤ 2000) və m qapıların sayını (1 ≤ m ≤ 10000) göstərir. Sonrakı m sətirdə qapıların təsviri verilir - hansı otaqdan başladığı, hansı otağa apardığı (qapılardan yalnız bir istiqamətdə keçmək mümkündür), və qapıdan keçərkən biliklərin miqdarına əlavə olunan tam ədəd (bu ədədin modulu 10000-dən çox deyil). Qapılar bir otaqdan özünə də apara bilər, iki otaq arasında bir neçə qapı ola bilər.
Çıxış məlumatları
Əgər məhdudiyyətsiz böyük bilik əldə etmək mümkündürsə, ":)" çıxarın, əgər labirinti keçmək mümkün deyilsə, ":(" çıxarın, və əks halda əldə edilə biləcək maksimum bilik miqdarını çıxarın.