7455: USACO 2020 February Contest, Gold —— Problem 1. Timeline
[Creator : ]
Description
Bessie 在过去的 $M$ 天内参加了 $N$ 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。
对于第 $i$ 次挤奶，Bessie 记得它不早于第 $S_i$ 天进行。另外，她还有 $C$ 条记忆，每条记忆形如一个三元组 $(a,b,x)$，含义是第 $b$ 次挤奶在第 $a$ 次挤奶结束至少 $x$ 天后进行。
现在请你帮 Bessie 算出在满足所有条件的前提下，每次挤奶的最早日期。
保证 Bessie 的记忆没有错误，这意味着一定存在一种合法的方案，使得：
- 第 $i$ 次挤奶不早于第 $S_i$ 天进行，且不晚于第 $M$ 天进行；
- 所有的记忆都得到满足；
对于第 $i$ 次挤奶，Bessie 记得它不早于第 $S_i$ 天进行。另外，她还有 $C$ 条记忆，每条记忆形如一个三元组 $(a,b,x)$，含义是第 $b$ 次挤奶在第 $a$ 次挤奶结束至少 $x$ 天后进行。
现在请你帮 Bessie 算出在满足所有条件的前提下，每次挤奶的最早日期。
保证 Bessie 的记忆没有错误，这意味着一定存在一种合法的方案，使得：
- 第 $i$ 次挤奶不早于第 $S_i$ 天进行，且不晚于第 $M$ 天进行；
- 所有的记忆都得到满足；
Input
第一行三个整数 $N,M,C$。保证 $1 \leq N,C \leq 10^5$，$2 \leq M \leq 10^9$。
接下来一行包含 $N$ 个整数 $S_1, S_2 , \ldots, S_n$，保证 $\forall 1 \leq i \leq n$，都满足 $1 \leq S_i \leq M$。
下面 $C$ 行每行三个整数 $a,b,x$，描述一条记忆。保证 $a \neq b$，且 $1 \leq x \leq M$。
接下来一行包含 $N$ 个整数 $S_1, S_2 , \ldots, S_n$，保证 $\forall 1 \leq i \leq n$，都满足 $1 \leq S_i \leq M$。
下面 $C$ 行每行三个整数 $a,b,x$，描述一条记忆。保证 $a \neq b$，且 $1 \leq x \leq M$。
Output
输出 $N$ 行，每行一个整数，第 $i$ 行的数表示第 $i$ 次挤奶的最早日期。
Constraints
测试点 $2 \sim 4$ 满足 $N,C \leq 10^3$。
测试点 $5 \sim 10$ 没有特殊限制。
测试点 $5 \sim 10$ 没有特殊限制。
Sample 1 Input
4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4
Sample 1 Output
1
6
3
8