佛曰：皤羅梵喝陀想迦實吉即侄真夷究曳南罰三麼俱姪等梵盧隸呐神呐吉梵以呐數盡悉般俱至心冥寫所怖奢姪切想怛奢沙缽室怯是等藝輸諳夜呐佛侄朋利俱特蒙冥想他道夢故奢等喝罰夜盡皤即咒侄大諳阿穆彌依故
区间连有向边，边长形如等差数列
每一组边有一个共同的起始点 $ x $ ，终点落在区间$[l, r]$内。其中 $ x $ 号点向 $ l + k $ 号点连的边权值为 $ s + kd $ （$ 0 \leq k \leq r - l $ ）
求源点为 $ 1 $ 的单源最短路
输入格式
第一行两个整数$ n, m $，代表点数和边的组数
接下来$ m $行每行$ 5 $个整数$ x, l, r, s, d $描述一组边，分别代表单向边起点，单向边终点区间左端点，单向边终点区间右端点，等差数列首项，等差数列公差
输出格式
一行$ n $个整数，第$ i $个整数代表$ 1 $至$ i $的最短路长度，若不存在路径则输出$ -1 $
样例一
input
5 3 2 3 5 6 -2 1 2 4 1 6 4 3 3 1 1
output
0 1 6 5 3
样例解释
无可奉告，下同。
样例二
input
5 5 1 3 4 125 398 3 2 4 559 -107 1 1 5 597 -104 5 3 5 368 448 2 2 3 141 692
output
0 493 125 285 181
数据范围与约定
子任务1 (6 pts): $1 \leq n \leq 500, 0 \leq m \leq 500$
子任务2 (21 pts): $1 \leq n \leq 5000, 0 \leq m \leq 5000$
子任务3 (29 pts): 所有 $ d $ 的绝对值相等
子任务4 (44 pts): 无额外限制
对于全部数据：$ 1 \leq n \leq 100000, 0 \leq m \leq 100000 $， $ 1 \leq x \leq n, 1 \leq l \leq r \leq n $
对于每一组边，设等差数列最小项为 $ z $ ，$ 0 \leq z \leq 10^8, -10^8 \leq d \leq 10^8 $
时间限制：$1\texttt{s}$
空间限制：$512\texttt{MB}$
