9445 - 拉近距离

在小明和小红的生活中,有 N 个关键的节点。有 M 个事件,记为一个三元组 (S_i,T_i,W_i),表示从节点 S_i 有一个事件可以转移到 T_i,事件的效果就是使他们之间的距离减少 W_i

这些节点构成了一个网络,其中节点 1N 是特殊的,节点 1 代表小明,节点 N 代表小红,其他代表进展的阶段。所有事件可以自由选择是否进行,但每次只能进行当前节点邻接的。请你帮他们写一个程序,计算出他们之间可能的最短距离。

输入

第一行,两个正整数 N,M

之后 M 行,每行 3 个空格隔开的整数 S_i,T_i,W_i

输出

一行,一个整数表示他们之间可能的最短距离。如果这个距离可以无限缩小,输出`Forever love`。

样例

输入

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

输出

-2

提示

数据范围

对于 20\% 数据,N \le 10M \le 50

对于 50\% 数据,N \le 300M \le 5000

对于 100\% 数据,1\le N \le 10^31\le M \le 10^4|W_i|\le 100,保证从节点 12 \dots N 有路径,从节点 N1 \dots N - 1 有路径。

时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题