拉近距离

题目背景

我是源点,你是终点。我们之间有负权环。 ——小明

题目描述

在小明和小红的生活中,有N个关键的节点。有M个事件,记为一个三元组(Si,Ti,Wi),表示从节点Si有一个事件可以转移到Ti,事件的效果就是使他们之间的距离减少Wi。 这些节点构成了一个网络,其中节点1和N是特殊的,节点1代表小明,节点N代表小红,其他代表进展的阶段。所有事件可以自由选择是否进行,但每次只能进行当前节点邻接的。请你帮他们写一个程序,计算出他们之间可能的最短距离。

输入输出格式

输入格式


第1行,两个正整数N,M. 之后M行,每行3个空格隔开的整数Si,Ti,Wi。

输出格式


一行,一个整数表示他们之间可能的最短距离。如果这个距离可以无限缩小,输出“Forever love”(不含引号)。

输入输出样例

输入样例 #1

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

输出样例 #1

-2

说明

对于20%数据,N<=10,M<=50。 对于50%数据,N<=300,M<=5000。 对于全部数据,N<=1000,M<=10000,|Wi|<=100,保证从节点1到N有路径。