Ən yüksək bal#11445
Siz otaq və tuneldən ibarət bir oyun oynayırsınız. Başlanğıc hesabınız -dır və hər bir tunel hesabınızı qədər artırır, burada həm müsbət, həm də mənfi ola bilər. Tunellərdən bir neçə dəfə keçmək mümkündür.
Sizin məqsədiniz otaq -dən otaq -ə keçərək mümkün olan ən çox xalı toplamaqdır.
Birinci sətirdə iki tam ədəd n\:(1 \le n \le 2500) və m\:(1 \le m \le 5000) verilir: otaqların və tunellərin sayı. Otaqlar 1, 2, \dots , n ilə nömrələnib.
Sonra sətir gəlir, hər biri bir tuneli təsvir edir. Hər sətirdə üç tam ədəd , b\:(1 \le a, b \le n) və x\:(−10^9 \le x \le 10^9) var: tunel otaq -da başlayır, otaq -də bitir və hesabınızı qədər artırır. Bütün tunellər birtərəflidir.
Məlumdur ki, otaq -dən otaq -ə keçmək mümkündür.
Bir tam ədəd çıxarın: əldə edə biləcəyiniz ən çox xal. Lakin, əgər istənilən qədər böyük xal əldə edə bilsəniz, çıxarın.
Nümunə 1