T44251 探访

彗星即将到来，而这时，三叶要前往东京与泷见面。三叶的零花钱所剩不多了，从糸守到东京的车票又有点贵；她统计了JR的列车数据，你能帮助她花尽量少的钱买到车票吗？

JR的铁路网上有$n$个车站，三叶把它们分别编号为$1,2,\cdots ,n$，其中$1$号车站为糸守，$n$号车站为东京。当天共有$m$趟单向列车，其中的第$i(1\le i \le m)$趟列车由$u_{i}$号车站始发，途经的铁路长度为$w_{i}$千米，每千米车票费用为$k_{i}$元，最终到达$v_{i}$号车站。注意，数据**不**保证$u_{i}\neq v_{i}$。不考虑列车的发车时间。 为了节省时间，三叶决定只乘火车，可以乘坐列车直达东京（即乘坐一趟$u_{i}=1, v_{i}=n$的列车），也可以乘坐若干趟列车中转。 JR的车票费用计算方法很特别。如果三叶乘坐的所有列车途经的铁路**总**长度为$l=\sum w_{i}$，且所有列车每千米车票费用的**最大值**为$k_{max}$，则需要支付的车票费用为$l\times k_{max}$。 你能帮助三叶求出从糸守到东京的最低车票费用吗？

输入共$(m+1)$行。 第一行有$2$个正整数，分别为车站的个数（包括东京和糸守）$n$和列车的数量$m$。 接下来$m$行，每一行含有$4$个正整数，第$i$行的$4$个正整数$u_{i},v_{i},w_{i},k_{i}$分别代表列车始发的车站序号、到达的车站序号、途经长度和每千米收费。

输出共$1$行，含$1$个正整数，表示从糸守（$1$号车站）到东京（$n$号车站）的最低费用。

对于5%的数据，满足$n\le 10, m\le 10, k_{i} \le 5$。 对于另外5%的数据，满足$n\le 20, m\le 100, k_{i} \le 10$。 对于另外10%的数据，满足$n\le 100, m\le 10000,k_{i}=1$。 对于另外10%的数据，满足$n\le 10000, m\le 500000$，所有$k_{i}$相等。 对于另外10%的数据，满足$n\le 1000, m\le 50000, k_{i} \le 100$。 对于另外20%的数据，满足$n\le 10000, m\le 500000, k_{i} \le 100$。 对于另外20%的数据，满足$n\le 10000, m\le 500000, k_{i} \le 10000$。 对于另外20%的数据，满足$n\le 10000, m\le 500000, k_{i} \le 500000$。  ----- 对于50%的数据，保证数据随机。 对于100%的数据，满足$1\le u_{i},v_{i} \le n, 1\le w_{i} \le 2000$，保证从$1$号车站一定能到达$n$号车站，保证数据由[CYaRon](https://www.luogu.org/discuss/show?postid=11410)生成。 ----- 样例1解释：乘坐从$1$号车站到$4$号车站的列车（$1\rightarrow 4$），总长度为$4$千米（$l=4$），每千米费用的最大值为$1$（$k_{max}=1$），总费用为$4$。 样例2解释：$1\rightarrow 2\rightarrow 4$，$l=3$，$k_{max}=2$，总费用为$6$。 样例3解释：$1\rightarrow 4 \rightarrow 5$，$l=612$，$k_{max}=10$，总费用为$6120$。