Найвищий бал#11445
Ви граєте в гру, яка складається з кімнат і тунелів. Ваш початковий рахунок дорівнює , і кожен тунель додає до нього значення , яке може бути як додатним, так і від'ємним. Ви можете проходити через один і той самий тунель кілька разів.
Ваше завдання — дістатися з кімнати до кімнати . Яку максимальну кількість очок Ви можете отримати?
Перший рядок містить два цілі числа n\:(1 \le n \le 2500) і m\:(1 \le m \le 5000): кількість кімнат і тунелів. Кімнати пронумеровані від до .
Наступні рядків описують тунелі. Кожен рядок містить три цілі числа , b\:(1 \le a, b \le n) і x\:(−10^9 \le x \le 10^9): тунель починається в кімнаті , закінчується в кімнаті і збільшує ваш рахунок на . Усі тунелі є односторонніми.
Відомо, що з кімнати можна дістатися до кімнати .
Виведіть одне ціле число: максимальну кількість очок, яку можна отримати. Якщо ж існує можливість отримати нескінченно велику кількість очок, виведіть .
Приклад 1