题目描述
给定一张 $ n $ 个点 $ m $ 条边的有向图。
对于每条边 $ (u, v, r, p) $ 表示有一条从 $ u $ 到 $ v $ 的边，走过前必须至少持有 $ r $ 元钱，走过后会增加 $ p $ 元钱。
分别求出从每个点出发能够无限地游走下去所需要最少的最初钱数。特别地，若从这个点以任意最初钱数出发都无法无限游走下去则输出 $ -1 $ 。
输入格式
从文件 lan.in 中读入数据。
输入 $ m + 1 $ 行。
其中第一行两个整数 $ n $ ，$ m $ ，分别表示无向图的点数和边数。
接下来$ m $ 行，每行四个非负整数 \(u_i, v_i, r_i, p_i\) ，含义如上文所述，描述一条有向边。
输出格式
输出到文件 lan.out 中。
输出一行 $ n $ 个数，表示每个点的答案。
样例
样例 1
样例 1 输入（lan/ex_lan1.in)
5 7
1 2 0 1
2 1 10 2
2 3 1 3
3 4 5 2
4 2 2 4
3 5 1 5
4 5 0 3
样例 1 输出（lan/ex_lan1.ans)
1 2 5 2 -1
样例2
见附加文件中的 lan/ex_lan2.in 与 lan/ex_lan2.ans。
该样例满足测试点 2 的限制。
样例3
见附加文件中的 lan/ex_lan3.in 与 lan/ex_lan3.ans。
该样例满足测试点 3 的限制。
样例4
见附加文件中的 lan/ex_lan4.in 与 lan/ex_lan4.ans。
该样例满足测试点 4 的限制。
数据范围与提示
【数据范围】
对于 \(100\%\) 的数据：满足 $1 \leq n \leq m \leq 2 \times 10 ^5, 0 \leq r_i,p_i \leq 1 \times 10 ^9 $
【评测方式 & 得分规则】
对于每个测试点，采用 全文比较（过滤行末空格及文末回车） 评测方式。
| 测试点编号 | n | m | 特殊性质 |
|---|---|---|---|
| 1 | \(\leq 5\) | \(\leq\) 15 | 无 |
| 2 | \(\leq 5\) | \(\leq\) 15 | 无 |
| 3 | \(\leq 2000\) | \(\leq 2000\) | 无 |
| 4 | \(\leq 2000\) | \(\leq 2000\) | 无 |
| 5 | \(\leq 200000\) | \(\leq 200000\) | A |
| 6 | \(\leq 200000\) | \(\leq 200000\) | A |
| 7 | \(\leq 200000\) | \(\leq 200000\) | 无 |
| 8 | \(\leq 200000\) | \(\leq 200000\) | 无 |
| 9 | \(\leq 200000\) | \(\leq 200000\) | 无 |
| 10 | \(\leq 200000\) | \(\leq 200000\) | 无 |
特殊性质 A: \(\forall i \in [1,m]\) ,\(r_i = 0\) 。