CF366D.Dima and Trap Graph

Dima and Inna love spending time together. The problem is, Seryozha isn't too enthusiastic to leave his room for some reason. But Dima and Inna love each other so much that they decided to get criminal...

Dima constructed a trap graph. He shouted: "Hey Seryozha, have a look at my cool graph!" to get his roommate interested and kicked him into the first node.

A trap graph is an undirected graph consisting of n nodes and m edges. For edge number k, Dima denoted a range of integers from l__k to r__k (l__k ≤ r__k). In order to get out of the trap graph, Seryozha initially (before starting his movements) should pick some integer (let's call it x), then Seryozha must go some way from the starting node with number 1 to the final node with number n. At that, Seryozha can go along edge k only if l__k ≤ x ≤ r__k.

Seryozha is a mathematician. He defined the loyalty of some path from the 1-st node to the n-th one as the number of integers x, such that if he initially chooses one of them, he passes the whole path. Help Seryozha find the path of maximum loyalty and return to his room as quickly as possible!

迪马和英娜非常喜欢待在一起。问题是，谢廖沙出于某种原因不太愿意离开自己的房间。但迪马和英娜彼此深爱，于是他们决定“干一票大的”……

迪马构造了一张陷阱图。他大喊：“嘿，谢廖沙，快来看看我这张酷炫的图！”以此吸引室友注意，并把他一脚踢进了第一个节点。

一张陷阱图是一张包含 $n$ 个节点和 $m$ 条边的无向图。对于第 $k$ 条边，迪马标定了一个整数区间 $[l_k, r_k]$（满足 $l_k \leq r_k$）。为了逃出这张陷阱图，谢廖沙需在出发前（即开始移动之前）选定某个整数（记为 $x$），然后必须从编号为 $1$ 的起始节点出发，沿某条路径到达编号为 $n$ 的终点节点。在此过程中，谢廖沙仅当满足 $l_k \leq x \leq r_k$ 时，才允许经过第 $k$ 条边。

谢廖沙是一位数学家。他将从第 $1$ 个节点到第 $n$ 个节点的某条路径的忠诚度定义为：满足“若初始选定该整数 $x$，则可完整通行整条路径”的整数 $x$ 的个数。请帮助谢廖沙找出忠诚度最大的路径，以便他能尽快返回自己的房间！

The first line of the input contains two integers n and m (2 ≤ n ≤ 103, 0 ≤ m ≤ 3·103). Then follow m lines describing the edges. Each line contains four integers a__k, b__k, l__k and r__k (1 ≤ a__k, b__k ≤ n, 1 ≤ l__k ≤ r__k ≤ 106). The numbers mean that in the trap graph the k-th edge connects nodes a__k and b__k, this edge corresponds to the range of integers from l__k to r__k.

Note that the given graph can have loops and multiple edges.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^3$，$0 \leq m \leq 3\cdot10^3$）。接下来是 $m$ 行，每行描述一条边。每行包含四个整数 $a_k$、$b_k$、$l_k$ 和 $r_k$（$1 \leq a_k,\,b_k \leq n$，$1 \leq l_k \leq r_k \leq 10^6$）。这些数字表示：在该陷阱图中，第 $k$ 条边连接节点 $a_k$ 和 $b_k$，且该边对应整数区间 $[l_k,\,r_k]$。

注意：给定的图可能包含自环和重边。

In a single line of the output print an integer — the maximum loyalty among all paths from the first node to the n-th one. If such paths do not exist or the maximum loyalty equals 0, print in a single line "Nice work, Dima!" without the quotes.

在输出的一行中打印一个整数——所有从第一个节点到第 $n$ 个节点的路径中的最大忠诚度。如果不存在这样的路径，或者最大忠诚度等于 0，则在一行中输出 "Nice work, Dima!"（不带引号）。

Explanation of the first example.

Overall, we have 2 ways to get from node 1 to node 4: first you must go along the edge 1-2 with range [1-10], then along one of the two edges 2-4.

One of them contains range [3-5], that is, we can pass through with numbers 3, 4, 5. So the loyalty of such path is 3.

If we go along edge 2-4 with range [2-7], then we can pass through with numbers 2, 3, 4, 5, 6, 7. The loyalty is 6. That is the answer.

The edge 1-2 have no influence on the answer because its range includes both ranges of the following edges.

第一个示例的解释。

总体而言，我们有 2 种方式从节点 1 到达节点 4：首先必须沿边 $1\text{-}2$（其取值范围为 $[1\text{-}10]$）行进，然后沿两条边 $2\text{-}4$ 中的一条行进。

其中一条边 $2\text{-}4$ 的取值范围为 $[3\text{-}5]$，即我们可使用数字 $3, 4, 5$ 通过该边。因此该路径的忠诚度为 $3$。

若我们沿另一条边 $2\text{-}4$（其取值范围为 $[2\text{-}7]$）行进，则可使用数字 $2, 3, 4, 5, 6, 7$ 通过该边，忠诚度为 $6$。此即答案。

边 $1\text{-}2$ 对答案无影响，因为它的取值范围 $[1\text{-}10]$ 同时包含了后续两条边的所有取值范围。