Description

In the lives of Xiao Ming and Xiao Hong, there are $N$ key nodes. There are $M$ events, denoted as a triplet $(S_i, T_i, W_i)$, meaning that from node $S_i$ there is an event that can move to $T_i$, and the effect of the event is to reduce the distance between them by $W_i$.

These nodes form a network, in which nodes $1$ and $N$ are special: node $1$ represents Xiao Ming, node $N$ represents Xiao Hong, and the others represent stages of progress. You may freely choose whether to perform each event, but at any step you may only perform an event that is outgoing from the current node. Please write a program to compute the shortest possible distance between them.

Input Format

The first line contains two positive integers $N, M$.

Then follow $M$ lines, each containing $3$ space-separated integers $S_i, T_i, W_i$.

Output Format

Output one line with a single integer representing the shortest possible distance between them. If this distance can be decreased without bound, output Forever love.

3 3
1 2 3
2 3 -1
3 1 -10

-2

Hint

For $20\%$ of the testdata, $N \le 10$, $M \le 50$.

For $50\%$ of the testdata, $N \le 300$, $M \le 5000$.

For $100\%$ of the testdata, $1 \le N \le 10^3$, $1 \le M \le 10^4$, $|W_i| \le 100$. It is guaranteed that there is a path from node $1$ to every node $2 \dots N$, and from node $N$ to every node $1 \dots N - 1$.

Translated by ChatGPT 5