Bobo 居住在大城市 ICPCCamp。

ICPCCamp 有 $n$ 个地铁站，用 $1, 2, \dots, n$ 编号。 $m$ 段双向的地铁线路连接 $n$ 个地铁站，其中第 $i$ 段地铁属于 $c_i$ 号线，位于站 $a_i, b_i$ 之间，往返均需要花费 $t_i$ 分钟（即从 $a_i$ 到 $b_i$ 需要 $t_i$ 分钟，从 $b_i$ 到 $a_i$ 也需要 $t_i$ 分钟）。

众所周知，换乘线路很麻烦。如果乘坐第 $i$ 段地铁来到地铁站 $s$，又乘坐第 $j$ 段地铁离开地铁站 $s$，那么需要额外花费 $|c_i - c_j|$ 分钟。注意，换乘只能在地铁站内进行。

Bobo 想知道从地铁站 $1$ 到地铁站 $n$ 所需要花费的最小时间。

输入

输入包含不超过 $20$ 组数据。

每组数据的第一行包含两个整数 $n, m$ ($2 \leq n \leq 10^5, 1 \leq m \leq 10^5$).

接下来 $m$ 行的第 $i$ 行包含四个整数 $a_i, b_i, c_i, t_i$ ($1 \leq a_i, b_i, c_i \leq n, 1 \leq t_i \leq 10^9$).

保证存在从地铁站 $1$ 到 $n$ 的地铁线路（不一定直达）。

输出

对于每组数据，输出一个整数表示要求的值。

样例输入

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

样例输出

1
3
2