Masala #VARLIZZ388

Sizga n ta tugun va m qirrali vaznli yo'naltirilgan asiklik grafik (DAG) beriladi. Har bir tugun 0 dan n-1 gacha etiketlanadi. Sizning vazifangiz 0-tugundan boshlab va n-1 -tugunda tugaydigan maksimal yo'l yig'indisini topishdir. Yo'l istalgan miqdordagi oraliq tugunlarga tashrif buyurishi mumkin, lekin har bir tugunga ko'pi bilan bir marta tashrif buyurish mumkin.

Birinchi qatorda ikkita butun son n va m \((1<=n<=10^5)\)\((1<=m<=2*10^5)\), grafikdagi tugunlar va qirralarning soni mavjud. Keyingi m satrlarning har biri uchta butun sondan u, v \((-10^3<=w<=10^3)\)va wdan iborat bo'lib, u tugundan v tugungacha bo'lgan yo'naltirilgan chetni w og'irligi bilan ifodalaydi.

Bitta butun son, 0-tugundan n-1 -tugungacha bo'lgan maksimal yo'l yig'indisi. Agar bunday yo'l bo'lmasa, -1 chiqaring.