题目描述

译自 ICPC PacificNW 2017 H Avoiding Airports

David 要完成一个旅行计划，这个计划要在 $n$ 个城市中选择一个乘坐飞机的方案。他在时刻 0 从第 $1$ 个城市出发，最后到达 $n$ 号城市。
城市分别编号为 $1\dots n$。城市之间由 $m$ 条航班线路相连。
David 已经查看了这些航班的时刻表，第 $i$ 个航班将从城市 $u_i$ 飞往城市 $v_i$，在时刻 $s_i$ 起飞，时刻 $e_i$ 到达。
David 是一个很讨厌等待的人，他在等待过长时间后会有挫败感。如果他在机场等待了 $t$ 的时间，他将感到 $t^2$ 的挫败感。
请帮助 David 规划一个挫败感之和最小的路线，不一定花的时间最短，只需要最让他舒服就行了（他真的很讨厌等待！）。

保证不存在两个航班起飞时间相同，保证不存在两个航班到达时间相同。

输入格式

第一行两个整数 $n$，$m$ 分别表示城市的数目，航班的数目。
接下来 $m$ 行是航班的信息，第 $i + 1$ 行四个整数，$u_i,$ $v_i,$ $s_i,$ $e_i$。

输出格式

一行一个数，答案。

5 8
1 2 1 10
2 4 11 16
2 1 9 12
3 5 28 100
1 2 3 8
4 3 20 21
1 3 13 27
3 5 23 24

12

3 5
1 1 10 20
1 2 30 40
1 2 50 60
1 2 70 80
2 3 90 95

1900

数据范围与提示

$2 \leq n \leq 2\times 10^5,$ $1 \leq m \leq 2\times 10^5,$ $1 \leq u_i,v_i \leq n,$ $0 \leq s_i , e_i \leq 10^6$。

数据保证不存在两个航班起飞时间相同，保证不存在两个航班到达时间相同。