You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

RIDL好想出去玩，但TA精力有限，不能连续玩太多个地方。

RIDL在网上看到了$\ n\$个地点的游玩攻略，这$\ n\$个地点之间共有$\ m\$条双向路线，第$\ i\$条路线连通地点$\ u_i\$和$\ v_i\$，RIDL从任意方向走过第$\ i\$条线路所需的时长为$\ t_i\$小时。

同时，RIDL还得知游玩第$\ i\$个地点的开心值为$\ h_i\$点，治愈值为$\ r_i\$小时。

RIDL在游玩的过程中会累积疲劳值，初始的疲劳值为$\ 0\$，在整个游玩过程中疲劳值必须小于等于$\ H\$。

行动过程如下：

RIDL可以任意次（也有可能是$\ 0\$次）在任意地点$\ x\$休息：

• 每次消耗$\ r_x\$小时，疲劳值重置为$\ 0\$，位置不变

当RIDL从地点$\ x\$到地点$\ y\$：

• 如果游玩地点$\ x\$比地点$\ y\$的开心值高，RIDL走完这条路后的疲劳值会减少到$\ 0\$
• 如果游玩地点$\ x\$比地点$\ y\$的开心值低或相等，RIDL走完这条路后的疲劳值会累积$\ h_y-h_x\$
• 过程中任意时刻都必须满足疲劳值小于等于$\ H\$，否则不能走这条路

现在RIDL从1号地点出发，只能在原地休息或通过这些线路在地点间移动。对于每个地点，RIDL想知道TA最快需要多少小时可以到达该地点，或永远无法到达？

Input Format

第一行包含三个正整数$\ n, m, H \ (2≤n≤10^4,\ 0≤m≤2\times 10^4,\ 1≤H≤100)$，分别表示城市的个数，线路的条数，以及RIDL能接受的最大疲劳值。

第二行包含$\ n\$个正整数$\ h_1,h_2,\dots,h_n\ (1≤h_i≤10^9)$，代表游玩每个地点的开心值。

第三行包含$\ n\$个正整数$\ r_1,r_2,\dots,r_n\ (1≤r_i≤10^9)$，代表游玩每个地点的治愈值。

接下来$\ m\$行，每行三个正整数$\ u_i,v_i,t_i \ (1≤u_i,v_i≤n,\ u_i \neq v_i,\ 1≤t_i≤10^9)$，代表一条线路连接的两个地点和所需的时长。

Output Format

输出一行$\ n\$个整数，第$\ i\$个整数代表RIDL到达第$\ i\$号景点所需的最短时间（以小时为单位）。如果RIDL永远无法到达该景点，输出$\ -1\$。

Sample

输入

7 8 3
1 2 3 4 5 6 7
1 20 5 3 3 30 25
1 2 1
2 4 10
1 3 8
2 3 2
3 5 9
4 3 100
3 7 2
3 6 7

输出

0 1 3 11 16 15 -1 

Hint

在样例中，各节点最短时间如下：

$1：$初始节点，无需额外时间

$2：$经过节点$\ 1-2，$消耗时间为$\ 2$

$3：$经过节点$\ 1-2-3，$消耗时间为$\ 1+2=3$

$4：$经过节点$\ 1-2-4，$消耗时间为$\ 1+10=11$

$5：$经过节点$\ 1-2-3-2-3-5，$消耗时间为$\ 1+2+2+2+9=16$

$6：$经过节点$\ 1-2-3$（休息）$-6，$消耗时间为$\ 1+2+5+7=15$

$7：$无法到达