问题描述

这里是某个丛林，你的朋友---变色龙生活在这里。

丛林中有N个广场，每个广场都有一个从1到N的编号。此外，丛林中有M条道路，每条道路都有一个从1到M的编号。每条道路连接两个不同的广场，可以双向移动。

你的朋友变色龙打算参加CODE THANKS FESTIVAL 2015，并计划从广场1前往广场N。变色龙在移动广场之间时会使用道路，但是丛林中的道路充满了未知的危险，因此当使用道路i（1≦i≦M）时，变色龙的体色必须为颜色ci。此外，使用道路i进行移动需要时间ti。

当变色龙从广场1开始移动时，它的体色是颜色1。变色龙可以改变任何广场的体色，但是在任何广场上，将体色从颜色x改变为颜色y，需要花费时间| x-y |。此外，如果变色龙到达广场N，则结束移动，此时它的体色可以是任何颜色。

现在，你需要求出变色龙到达广场N所需的最小时间。

输入

输入以以下格式从标准输入中给出。

N M a1 b1 c1 t1 a2 b2 c2 t2 : aM bM cM tM

• 第一行包含两个整数，广场的个数N（2 ≤ N ≤ 40,000）和道路的数量M（1 ≤ M ≤ 80,000），以空格分隔。
• 接下来的M行给出与道路相关的信息。在这些信息中，第i（1≦i≦M）行以空格分隔给出四个整数值ai，bi（1≤ai<bi≤N），ci（1≤ci≤1,000,000,000）和ti（1≤ti≤1,000,000,000）。表示道路i连接广场ai和bi，通过道路i时体色必须为颜色ci，并且需要花费时间为ti。
• 对于任意的i ≠ j，都满足ai ≠ aj或bi ≠ bj。
• 保证可以从广场1到达其他任何广场。

输出

输出作为变色龙达到广场N所需的最小时间，以单独的一行输出。输出末尾包括一个换行符。

输入示例1

6 7
1 2 1 6
1 3 7 4
2 3 3 4
2 5 6 6
3 4 4 6
3 5 1 3
5 6 2 4

输出示例1

22

对于这个输入示例，最佳移动方式如下：

• 初始时，广场1上有体色为颜色1的变色龙。
• 使用道路1从广场1到广场2移动。因为变色龙的体色是颜色1，所以可以移动，总共需要6个单位的时间。
• 在广场2上，将体色从颜色1更改为颜色3。总共需要6 + 2 = 8个单位的时间。
• 使用道路3从广场2到广场3移动。因为变色龙的体色是颜色3，所以可以移动，总共需要8 + 4 = 12个单位的时间。
• 在广场3上，将体色从颜色3更改为颜色1。总共需要12 + 2 = 14个单位的时间。
• 使用道路6从广场3到广场5移动。因为变色龙的体色是颜色1，所以可以移动，总共需要14 + 3 = 17个单位的时间。
• 在广场6上，将体色从颜色1更改为颜色2。总共需要17 + 1 = 18个单位的时间。
• 使用道路7从广场5到广场6移动。因为变色龙的体色是颜色2，所以可以移动，总共需要18 + 4 = 22个单位的时间。

输入示例2

3 3
1 2 1 10
1 3 3 3
2 3 5 2

输出示例2

5