Description

农夫约翰最近在网上购买了一辆新车，但由于匆忙，他在选择汽车的额外功能时不小心点击了两次“提交” 按钮，结果车上配备了两个 GPS 导航系统！更糟糕的是，这两个系统经常对约翰应该走的路线做出相互矛盾的决定。

约翰所在地区的地图由 $N$ 个交叉路口 $(2 \le N \le 10,000)$ 和 $M$ 条单向道路 $(1 \le M \le 50,000)$ 组成。道路 $i$ 连接交叉路口 $A_i(1 \le A_i \le N)$ 和 $B_i(1 \le B_i \le N)$。同一对交叉路口之间可能有多条道路连接，双向道路（允许双向通行）由两个相反方向的单向道路表示。约翰的家位于交叉路口 $1$，他的农场位于交叉路口 $N$。可以通过沿着一系列单向道路从他的家到达农场。

两个 GPS 单元使用的是上述相同的基础地图；然而，它们对每条道路的行驶时间有不同的看法。第一个 GPS 单元认为，道路 $i$ 需要 $P_i$ 个时间单位来行驶，而第二个单元认为，道路 $i$ 需要 $Q_i$ 个时间单位来行驶（每个行驶时间是范围在 $1$ 到 $10^5$ 的整数）。

约翰想从家里到农场。然而，每当约翰走一条（比如，从交叉路口 $X$ 到交叉路口 $Y$）GPS 单元认为不是从 $X$ 到农场的最短路线的一部分的道路时， GPS 单元就会大声抱怨（如果约翰走的道路两个 GPS 单元都不喜欢，两个 GPS 单元都会抱怨）。

请帮助约翰确定如果他适当地选择路线，他可以收到的最少总抱怨次数。如果约翰走的道路让两个 GPS 单元都抱怨，这将计为两次抱怨。

Input Format

第 $1$ 行：整数 $N$ 和 $M$。

接下来 $M$ 行，第 $i+1$ 行描述道路 $i$，有四个整数：$A_i,B_i,P_i,Q_i$。

Output Format

共一行，如果约翰从家到农场的路线选择最优，他可以收到的最少总抱怨次数。

5 7 
3 4 7 1 
1 3 2 20 
1 4 17 18 
4 5 25 3 
1 2 10 1 
3 5 4 14 
2 4 6 5 

1 

Hint

有 $5$ 个交叉路口和 $7$ 条单向道路。第一条道路从交叉路口 $3$ 连接到交叉路口 $4$；第一个 GPS 认为这条路需要 $7$ 个时间单位来行驶，而第二个 GPS 认为需要 $1$ 个时间单位，等等。

如果约翰走 $1 \to 2 \to 4 \to 5$ 的路径，那么第一个 GPS 会在 $1 \to 2$ 的道路上抱怨（它更喜欢 $1 \to 3$ 的道路）。然而，对于路径的其余部分 $2 \to 4 \to 5$，两个 GPS 都很满意，因为这对于每个 GPS 来说都是从 $2$ 到 $5$ 的最短路径。