You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

本人水平有限，中文翻译得可能不准确。看不懂中文翻译的看英文原文。

Description

Farmer John最近在网上买了一辆新车，但是他在设置扩充功能时偶然地点了两次“提交”按钮，结果他的车装备了两个GPS系统！更糟糕的是，这两个系统经常对Farmer John 的路径给出互相冲突的决定。

Farmer John所住地区的地图由N(2<=N<=10,000)个交点和M条有向线段组成。

路i连接了A_i和B_i两点。 几条道路可以连接同一对点，且一条双向通路被分离表示为两条方向相反的有向路径。

Farmer John的房子在交点1的位置上，而他的农场在点N。

已知可以从Farmer John的房子通过一个有向路径的序列到达农场，两个GPS都在用同一个地图（从上方俯瞰）；然而，它们对于走每条路的观念不一样。对于第一个GPS，路i需要用P_i单位的时间，而对于第二个GPS，同样是路i却需要Q_i单位的时间。(每个行进时间段长度都在区间[1, 100,000]中，且为整数) Farmer John想要从他的房子去他的农场。

然而，无论何时当Farmer John走某条路（也就是说，从点X到Y），会有GPS单位大声抱怨它认为这条路不是最短路的一部分，这让Farmer John很不爽。

(梁老师: “当走的边不是GPS认为的最短路的一部分时，GPS会吵???大概是这个意思, 如果我没有理解错题意的话。如果走错了？那就从当前点开始重新算最短路？我不知道，好好斟酌？”)

（当Farmer John走了一条两个GPS都不喜欢的路时，两个GPS都会抱怨）请计算Farmer John如果适当地自己选择路线，他一路上会收到的最少抱怨次数，如果两个GPS同时抱怨，那么总抱怨次数+2（换句话说，就是叫你算两个独立GPS抱怨次数之和）

Format

Input

第一行：整数N、M，一个空格隔开。

第i行：路i，用4个整数描述： A_i B_i P_i Q_i.

Output

仅一行，即最少抱怨次数。

Samples

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

样例解释

输入解释:有5个结点、7条有向路径。第一条路是从点3到点4，GPS1认为需要7单位时间，GPS2认为需要1单位时间，如此等等。