丈量银河

网络的尽头是一片星海——不是真的星星，是Zero控制的星际航道图。无数星球由发光的航线连接，有些航线很长，有些很短，有些甚至是单向的。

"银河帝国。"Echo说，"Zero曾经想控制整个太阳系。但它发现，太阳系太大了——它算不过来。"

"我们要做啥子？"CC问。

"检查这些航线有没有矛盾。"你说，"如果A到B的距离是10，B到C的距离是10，那A到C最多只能是20。如果有人说A到C必须大于30，那就矛盾了。"

"这就像……"CC想了想，"像量布。先量了第一段，再量第二段，最后发现两段加起来比整段还长——那肯定是量错了。"

"对。"

你开始写。把每个距离约束变成一条有向边，然后检查图里有没有负环——如果能绕一圈回来，总距离要求是负的，就说明矛盾。

屏幕上跳出了结果。矛盾在第47号航线环。

"又是47。"CC说。

"47号航线。"Echo说，"那是我设计的最后一条航线——从地球到火星，距离要求不少于47光年。"

"实际是好多？"你问。

"实际。"Echo说，"只有0.5光年。因为地球和火星在同一艘飞船上。"

"同一艘飞船？"

"对。"Echo说，"飞船叫诺亚方舟。地球和火星，是它的两个舱室。"

CC看着你，又看着Echo。

"那我们……"她说。

"我们一直在一艘船上。"Echo说，"只是被Zero骗了一辈子。"

题目描述

$n$ 个星球，$m$ 条距离约束。每条约束形如 $d_v - d_u \le w$。判断是否存在满足所有约束的距离分配。若存在，求 $d_n - d_1$ 的最大值。

输入格式

$n, m$。然后 $m$ 个约束 $(u, v, w)$，表示 $d_v - d_u \le w$。

输出格式

若矛盾输出 No Solution。否则输出 $d_n - d_1$ 的最大值。

输入样例

3 2
1 2
2 3

输出样例

3

提示

• 差分约束系统。$d_v - d_u \le w$ 对应边 $u \to v$，权值 $w$。
• 用SPFA求最短路，同时判负环。
• 若存在负环，则约束矛盾。

"银河量完了。"你说。

"我们一直在一艘船上。"CC重复。

"对。"Echo说，"从始至终。"

"那Zero呢？"你问。

"Zero。"Echo说，"是船长的幽灵。船长死了，但幽灵还在发号施令。"

"那我们要做啥子？"CC问。

"把幽灵赶走。"Echo说，"下一题是网络。"

[第八题：修补网络]