[CCO 2021] Travelling Merchant

题目描述

一个国家有 $n$ 个城市和 $m$ 条单向道路，一个旅行商在这些城市之间旅行。

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

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

输入格式

第一行，两个整数 $n, m$；

接下来 $m$ 行，第 $i$ 行有四个整数 $a_i, b_i, r_i, p_i$。

输出格式

一行，$n$ 个整数，若第 $i$ 个城市无解，第 $i$ 个整数为 $-1$；否则，为至少需要的初始资产（单位为元）。

输入输出样例

输入样例 #1

5 5
3 1 4 0
2 1 3 0
1 3 1 1
3 2 3 1
4 2 0 2

输出样例 #1

2 3 3 1 -1

说明/提示

样例 #1 解释

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

数据范围

对于 $\frac{2}{7}$ 的数据，$2 \leq n, m \leq 2 \times 10^3$；

对于另 $\frac{15}{49}$ 的数据，$p_i = 0$；

对于 $100\%$ 的数据，$2 \leq n, m \leq 2 \times 10^5$，$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$0 \leq r_i, p_i \leq 10^9$，保证没有自环但可能有重边。

题目来源

CCO2021 D2T1