Điểm Số Cao Nhất

Có $n$ phòng và $m$ đường hầm một chiều. Bắt đầu từ phòng $1$, mỗi đường hầm có điểm số (có thể âm). Tìm điểm số lớn nhất có thể đạt được khi đến phòng $n$. Nếu có thể đạt điểm số tùy ý lớn, in $-1$.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$, $b$, $x$ — đường hầm từ $a$ đến $b$ với điểm số $x$.

Dữ liệu ra

In điểm số lớn nhất có thể đạt khi đến phòng $n$, hoặc $-1$ nếu điểm số không bị giới hạn.

Ràng buộc

• $1\le n\le 2500$
• $1\le m\le 5000$
• $-{10}^9\le x\le {10}^9$

Ví dụ