AT_code_thanks_festival_2015_g カメレオン

在某个丛林中，你的朋友变色龙生活在那里。 丛林里有编号为 $1$ 到 $N$ 的 $N$ 个广场，并有 $M$ 条道路以编号 $1$ 到 $M$ 标识。每条道路都是双向的，连接着两个不同的广场。 为了参加 CODE THANKS FESTIVAL 2015，变色龙计划从广场 $1$ 出发前往广场 $N$。在丛林中移动时，变色龙会使用这些道路。然而，由于这些道路潜藏着未知的危险，要使用道路 $i\ (1 \le i \le M)$ 时，变色龙的体色必须是对应的颜色 $c_i$，并且使用这条道路需要花费 $t_i$ 时间。 起初，变色龙在广场 $1$ 的时候，体色是颜色 $1$。变色龙可以在任何一个广场改变体色，但若要把颜色从 $x$ 变为 $y$，需要耗费 $|x-y|$ 时间。在到达广场 $N$ 后，变色龙的旅程结束，此时体色可以是任意颜色。 你的任务是计算变色龙从广场 $1$ 到达广场 $N$ 所需要的最短时间。

输入通过标准输入给出： 第一行包含两个整数 $N\ (2 \le N \le 40,000)$ 和 $M\ (1 \le M \le 80,000)$，分别表示广场数量和道路数量。 接下来 $M$ 行，每行包含四个整数 $a_i$, $b_i\ (1 \le a_i < b_i \le N)$, $c_i\ (1 \le c_i \le 1,000,000,000)$, $t_i\ (1 \le t_i \le 1,000,000,000)$，表示道路 $i$ 连接广场 $a_i$ 和 $b_i$，通过这条道路时变色龙必须是颜色 $c_i$，且需要 $t_i$ 时间。 对于任意 $i \ne j$，我们有 $a_i \ne a_j$ 或 $b_i \ne b_j$。 可以通过一条或多条道路从广场 $1$ 到达所有其他广场。

输出变色龙从广场 $1$ 到达广场 $N$ 所需的最短时间，输出结果应换行。 ### 样例解释 1 在以下样例中，最优的路径为： 1. 初始时，变色龙位于广场 $1$，体色为颜色 $1$。 2. 使用道路 $1$ 从广场 $1$ 到广场 $2$。因为体色为颜色 $1$，所以可以通过，花费时间 $6$。 3. 在广场 $2$，将体色从颜色 $1$ 改为颜色 $3$，花费总时间 $6 + 2 = 8$。 4. 使用道路 $3$ 从广场 $2$ 走到广场 $3$，当前体色为颜色 $3$，花费时间 $8 + 4 = 12$。 5. 在广场 $3$，将体色由颜色 $3$ 变为颜色 $1$，花费总时间 $12 + 2 = 14$。 6. 使用道路 $6$ 从广场 $3$ 到广场 $5$，体色为颜色 $1$，花费时间 $14 + 3 = 17$。 7. 在广场 $5$，将体色从颜色 $1$ 改为颜色 $2$，花费总时间 $17 + 1 = 18$。 8. 使用道路 $7$ 从广场 $5$ 移动到广场 $6$，体色为颜色 $2$，花费时间 $18 + 4 = 22$。 **本翻译由 AI 自动生成**

### Sample Explanation 1 この入力例の場合、以下のように移動するのが最適です。 - 最初、広場 $ 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 $ となります。