题目描述

Berland 的首都是一座大城市，有 $n$ 个路口，编号为 $1$ 到 $n$。

城市里有 $m$ 条单向道路。第 $i$ 条道路从路口 $a_i$ 通向路口 $b_i$。某些道路有“延续道路”。如果汽车刚刚经过道路 $i$，接着从当前路口驶入道路 $j$，且道路 $j$ 是道路 $i$ 的延续，那么道路 $j$ 的行驶时间会比道路 $i$ 的实际行驶时间少 $1$ 秒；如果道路 $i$ 的实际行驶时间已经是 $0$，则道路 $j$ 的实际行驶时间仍为 $0$。

如果下一条路不是上一条路的延续，汽车需要减速转弯，于是这条路的行驶时间等于它的初始行驶时间。

每条道路 $i$ 有一个数 $d_i$ 表示它的延续道路：

• 若 $d_i=-1$，表示道路 $i$ 没有延续道路；
• 若 $d_i>0$，表示道路 $d_i$ 是道路 $i$ 的延续道路。

每条道路 $i$ 还具有初始行驶时间 $c_i$。沿某条路径行驶时，道路 $i$ 的实际时间按如下规则确定：

• 如果道路 $i$ 是路径上的第一条道路，或者道路 $i$ 不是上一条道路的延续，则实际时间为 $c_i$；
• 如果道路 $i$ 是上一条道路的延续，且上一条道路实际耗时为 $x$ 秒，则道路 $i$ 的实际时间为 $\max(0,x-1)$ 秒。

你在路口 $1$ 开了一家餐馆。请对每个路口求出从路口 $1$ 出发送餐到该路口所需的最短时间；如果无法到达，输出 -1。

输入格式

第一行包含三个整数 $n,m,g$，分别表示路口数、道路数和测试组编号。

接下来 $m$ 行，每行包含四个整数 $a_i,b_i,c_i,d_i$，描述第 $i$ 条道路：

• $a_i$：起点；
• $b_i$：终点；
• $c_i$：初始行驶时间；
• $d_i$：延续道路编号，若无延续道路则为 $-1$。

保证如果道路 $i$ 有延续道路，则该延续道路从 $b_i$ 出发。还保证若 $d_i\ne -1$，则 $c_{d_i} \ge c_i-1$。

注意：同一对路口之间可能有多条道路；一条道路可能是多条道路的延续；进入同一顶点的不同道路可能有不同的延续道路。

输出格式

输出一行 $n$ 个整数，第 $i$ 个数表示从路口 $1$ 到路口 $i$ 的最短送餐时间。若无法到达，输出 -1。

数据范围

$1 \le n,m \le 500000$，$0 \le g \le 10$，$1 \le a_i,b_i \le n$，$1 \le c_i \le 10^9$，$d_i=-1$ 或 $1 \le d_i \le m$。

样例

样例 1

3 2 0
1 2 5 2
2 3 10 -1

0 5 9

样例 2

5 4 0
1 2 5 4
3 4 10 -1
1 3 8 2
2 3 7 2

0 5 8 12 -1

样例 3

4 4 0
1 2 10 3
2 2 4 3
2 4 9 4
4 1 10 1

0 10 -1 17

样例 4

4 5 0
1 2 10 -1
1 3 1 3
3 4 7 4
4 2 6 5
2 2 5 5

0 1 1 1

样例解释

样例 1 中，到路口 $2$ 可走道路 $1$，耗时 $5$。到路口 $3$ 时，先走道路 $1$，再走道路 $2$。由于道路 $2$ 是道路 $1$ 的延续，第二段耗时为 $4$，总耗时为 $9$。

样例 2 中，到路口 $4$ 的一种最优路径为道路 $1,4,2$，耗时 $5+4+3=12$。路口 $5$ 不可达。

样例 3 中，到路口 $4$ 的最优路径为道路 $1,2,3$，耗时 $10+4+3=17$。

子任务