logo AlgoBeat OnlineJudge
登录 注册

#201112. 拉近距离

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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


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

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

输入格式

第一行,两个正整数

之后 行,每行 个空格隔开的整数

输出格式

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

样例

样例输入 1

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

样例输出 1

-2

数据范围与提示

对于 数据,

对于 数据,

对于 数据,,保证从节点 有路径,从节点 有路径。