德国有 \(N\) 个城市和 \(M\) 条单向道路，德芙在这些城市之间游走。

第 \(i\) 条道路从城市 \(a_i\) 到城市 \(b_i\) ，只有当德芙的资产不少于 \(r_i\) 元才可以走这条道路，走过这条道路之后德芙的资产会增加 \(p_i(\geq 0)\) 元。

德芙希望自己可以永远不停的游走下去，想知道从任意一个城市出发至少需要多少元初始资产。

第一行两个整数 \(N,M\) 。

接下来 \(M\) 行，每行四个整数 \(a_i,b_i,r_i,p_i\) ，保证没有自环但可能有重边。

输出一行 \(N\) 个整数，第 \(i\) 个整数表示从第 $ i$ 个城市出发至少需要多少元初始资产才能永远不停的游走下去。如果某个城市无解则它的答案是 \(-1\) 。

样例1解释

例如从第 \(2\) 座城市出发，初始资产 \(3\) 元，则可以在第 \(2,1,3\) 三座城市无限绕圈。

数据范围

所有测试数据：
\(2\leq N,M\leq 200\;000\)
\(1\leq a_i,b_i\leq N\) 且 \(a_i\neq b_i\)
\(0\leq r_i,p_i\leq 10^9\)

官方数据太多，只放了少量极限数据，你可以自己 去下载 完整数据包自行评测