P2136 Closing the Distance

I am the source, and you are the destination. There is a negative-weight cycle between us. — Xiao Ming.

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.

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 one line with a single integer representing the shortest possible distance between them. If this distance can be decreased without bound, output ``Forever love``.

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