D. RIDL好想出去玩

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

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

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

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

行动过程如下：

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

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

当RIDL从地点到地点：

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

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

第一行包含三个正整数，分别表示城市的个数，线路的条数，以及RIDL能接受的最大疲劳值。

第二行包含个正整数，代表游玩每个地点的开心值。

第三行包含个正整数，代表游玩每个地点的治愈值。

接下来行，每行三个正整数，代表一条线路连接的两个地点和所需的时长。

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

输入

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 

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

初始节点，无需额外时间

经过节点消耗时间为

经过节点消耗时间为

经过节点消耗时间为

经过节点消耗时间为

经过节点（休息）消耗时间为

无法到达