时之旅人注定是孤独的。
Doctor who 是一位时间旅行者，他经常在宇宙中进行旅行。宇宙中有许多星球，星球是他旅行的目的地。宇宙可以被看作是一张有向图，对于编号为 u,v 的两颗星球来说，它们之间有一条从 u 到 v 的有向边（保证 u<v），且经过该边需要经过 w 的时间（边的长度为 w）。同时，宇宙是在不断变化的，对于一条长度为 w 的边，这条边仅在时间轴中的 t 至 t+w 时间内存在，所以 Doctor who 必须恰好在 t 时刻从这条边的起点出发。
Doctor who 拥有一个能够穿梭时间的时光机器，该机器只能在某个星球上时使用，且每次进行时间穿梭都需要消耗一定的能量，即存在两个时间点 t1,t2 那么该机器从时间 t1 穿梭到时间 t2 所需要的能量是 ∣t1−t2∣+c（c是一个常数，对于每颗星球来说是不同的），并且使用时光机器后 Doctor who 的位置也不会变。
那么请问，假如 Doctor who 在任意一个时刻可以进行以下三件事之一：
且他在 0 时刻从星球 1 出发，那么他到达每个星球的时刻加上时光机消耗的能量的总和的最小值分别是多少。
第一行，一个整数 t(1≤t≤104)，代表数据组数。
对于每组数据：
第一行，两个整数 n,m(2≤n≤2⋅105;1≤m≤4⋅105)，代表宇宙中的星球数和连接星球的边数。
第二行，n 个整数 c1,…,cn(0≤ci≤109)，代表在每颗星球上进行时间穿梭消耗能量的常数。
接下来连续的 m 行，每行四个整数 ui,vi,wi,ti(1≤ui<vi≤n;1≤w≤109;0≤ti≤2⋅109)，代表连接有向边的两颗星球，边的长度和边存在的时间在时间轴上的起点。
保证同一测试点内 n 的总和不超过 2⋅105 且同一测试点内 m 的总和不超过 4⋅105。
对于每组数据：
输出共一行，n 个整数，即对于编号从 1 到 n 的每颗星球，输出一个整数，代表到达这颗星球的时刻加上时光机消耗的能量的和的最小值，如果 Doctor who 永远无法到达这颗星球，那么这个值就是 −1。
输入样例
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
输出样例
0 12
0 1 4
0 -1 9 13 -1 50 22 15
0 3000000000 5000000000 7000000000
样例解释
对于样例的第二组数据：
对于星球 1，Doctor who 从这出发，所以到达星球 1 的时刻为 0，时光机消耗的能量为 0，答案为 0+0=0。
对于星球 2，Doctor who 在时刻 0 从星球 1 出发，在边上消耗的时间为 1，所以到达星球 1 的时刻为 1，时光机消耗的能量为 0，答案为 1+0=0。
对于星球 3，Doctor who 在时刻 0 从星球 1 出发，消耗的时间为 1，所以到达星球 1 的时刻为 1；接下来，Doctor who 在星球 1 上使用时光机穿梭到时刻 0，消耗的能量为 ∣0−1∣+1=2；然后，Doctor who 在时刻 0 从星球 2 上出发，消耗的时间为 2，所以 Doctor who 在时刻 2 到达星球 3，所以答案为 2+2=4。
请注意，对于每一颗星球来说，答案都是独立计算的，即你可以认为有 n 个 Doctor who，他们分别从星球 1 出发，然后分别得到到达每个星球的时刻加上时光机消耗的能量的总和的最小值。