Migrated from Lutece 2610 IDA*

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

IDA 星是一棵在 A* 星系中的一颗 A 星。在 IDA 星上有 $n$ 个城市，城市之间有 $m$ 条无向道路。为啥 IDA 星叫 IDA 星呢，首先，IDA 星是一颗 A 星；其次，IDA 星距离 A 星星系的恒星非常遥远，所有城市之间的道路充满了冰（ice）和黑暗（dark）。你要从 $1$ 号城市驾车前往 $n$ 号城市，为了经过这些道路，你的车上需要装有足够的热和光。好在，我们已经探明了地图，知道了每条道路需要你的车上有多少热和光。注意，经过一条路并不会消耗你车上的热和光。请找到一条从 $1$ 号城市前往 $n$ 号城市的路径，使得车上需要装有的热和光之和最小。如果没有路径，请输出 $-1$。

Input

第一行两个整数 $n,m$，分别表示城市数量和道路数量。

接下来 $m$ 行，每行四个整数 $u,v,i,d$，$u,v$ 分别表示道路的两端，$i,d$ 分别表示经过道路所需要的热与光。

Output

一个整数，表示车上装载最少能到达 $n$ 的热与光之和。

Samples

4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17

32

3 1
1 2 1 1

-1

Constraints

$2\le n\le 50000$ $0\le m\le 100000$ $1\le u,v\le n$ $1\le i,d\le 50000$

Resources

2021 UESTC ICPC Training for Graph