E. Time Traveller
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

时之旅人注定是孤独的。

Doctor who 是一位时间旅行者，他经常在宇宙中进行旅行。宇宙中有许多星球，星球是他旅行的目的地。宇宙可以被看作是一张有向图，对于编号为 $$$u,v$$$ 的两颗星球来说，它们之间有一条从 $$$u$$$ 到 $$$v$$$ 的有向边（保证 $$$u \lt v$$$），且经过该边需要经过 $$$w$$$ 的时间（边的长度为 $$$w$$$）。同时，宇宙是在不断变化的，对于一条长度为 $$$w$$$ 的边，这条边仅在时间轴中的 $$$t$$$ 至 $$$t+w$$$ 时间内存在，所以 Doctor who 必须恰好在 $$$t$$$ 时刻从这条边的起点出发。

Doctor who 拥有一个能够穿梭时间的时光机器，该机器只能在某个星球上时使用，且每次进行时间穿梭都需要消耗一定的能量，即存在两个时间点 $$$t_1,t_2$$$ 那么该机器从时间 $$$t_1$$$ 穿梭到时间 $$$t_2$$$ 所需要的能量是 $$$|t_1-t_2|+c$$$（$$$c$$$是一个常数，对于每颗星球来说是不同的），并且使用时光机器后 Doctor who 的位置也不会变。

那么请问，假如 Doctor who 在任意一个时刻可以进行以下三件事之一：

1. 呆在某个星球上不动。 2. 在某条连接两个星球的边上移动。 3. 进行时空穿梭。

且他在 $$$0$$$ 时刻从星球 $$$1$$$ 出发，那么他到达每个星球的时刻加上时光机消耗的能量的总和的最小值分别是多少。

Input

第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。

对于每组数据：

第一行，两个整数 $$$n,m(2\le n \le 2\cdot 10^5;1\le m\le 4\cdot10^5)$$$，代表宇宙中的星球数和连接星球的边数。

第二行，$$$n$$$ 个整数 $$$c_1,\dots,c_n(0\le c_i\le 10^9)$$$，代表在每颗星球上进行时间穿梭消耗能量的常数。

接下来连续的 $$$m$$$ 行，每行四个整数 $$$u_i,v_i,w_i,t_i(1\le u_i \lt v_i\le n;1\le w\le 10^9;0\le t_i \le2\cdot 10^9)$$$，代表连接有向边的两颗星球，边的长度和边存在的时间在时间轴上的起点。

保证同一测试点内 $$$n$$$ 的总和不超过 $$$2\cdot 10^5$$$ 且同一测试点内 $$$m$$$ 的总和不超过 $$$4\cdot10^5$$$。

Output

对于每组数据：

输出共一行，$$$n$$$ 个整数，即对于编号从 $$$1$$$ 到 $$$n$$$ 的每颗星球，输出一个整数，代表到达这颗星球的时刻加上时光机消耗的能量的和的最小值，如果 Doctor who 永远无法到达这颗星球，那么这个值就是 $$$-1$$$。

Example
Input
4
2 1
9 16
1 2 4 8
3 3
0 1 0
1 2 1 0
2 3 2 0
1 3 1 8
8 10
3 0 1 2 5 0 8 0
1 3 9 0
3 8 5 2
7 8 11 90
2 5 1 0
1 8 7 15
2 4 1 0
3 4 3 10
2 5 9 16
4 6 25 25
1 7 6 16
4 3
1000000000 1000000000 1000000000 1000000000
1 2 1000000000 2000000000
2 3 1000000000 0
3 4 1000000000 0
Output
0 12
0 1 4
0 -1 9 13 -1 50 22 15
0 3000000000 5000000000 7000000000