luogu#P2136. 拉近距离

拉近距离

题目背景

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

题目描述

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

这些节点构成了一个网络,其中节点 11NN 是特殊的,节点 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

提示

对于 20%20\% 数据,N10N \le 10M50M \le 50

对于 50%50\% 数据,N300N \le 300M5000M \le 5000

对于 100%100\% 数据,1N1031\le N \le 10^31M1041\le M \le 10^4Wi100|W_i|\le 100,保证从节点 112N2 \dots N 有路径,从节点 NN1N11 \dots N - 1 有路径。