Description

Let $G$ be a weighted directed acyclic graph with $n$ vertices, labeled from $1$ to $n$. Design an algorithm to compute the longest path from $1$ to $n$ in $G$.

Input Format

The first line contains two integers, the number of vertices $n$ and the number of edges $m$.

Lines $2$ to $(m + 1)$ each contain three integers $u, v, w$ ($u<v$), indicating there is a directed edge from $u$ to $v$ with weight $w$.

Output Format

Output a single integer on one line, representing the length of the longest path from $1$ to $n$.

If $1$ cannot reach $n$, output $-1$.

2 1
1 2 1

1

Hint

Constraints

• For $20\%$ of the testdata, $n \leq 100$, $m \leq 10^3$.
• For $40\%$ of the testdata, $n \leq 10^3$, $m \leq 10^{4}$.
• For $100\%$ of the testdata, $1 \leq n \leq 1500$, $0 \leq m \leq 5 \times 10^4$, $1 \leq u, v \leq n$, $-10^5 \leq w \leq 10^5$.

Translated by ChatGPT 5