#1947. 拉近距离

拉近距离

题目描述

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

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

输入格式

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

之后 MM 行,每行 33 个空格隔开的整数 Si,Ti,WiS_i,T_i,W_i。

输出格式

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

样例

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

题目来源:洛谷 P2136