题目背景

你是一家快递公司的无人机调度员。城市可以看作一张由 $V$ 个路口和 $E$ 条双向道路组成的图。公司的无人机基地设在 $1$ 号路口。

今天有 $K$ 个加急订单。第 $i$ 个订单要求你把货物送到指定的路口 $target_i$。由于是无人机配送，完成这个订单需要消耗无人机的电池电量。

消耗的电量由两部分组成：

1. 飞行损耗：无人机从 $1$ 号路口飞到 $target_i$ 路口的最短路径距离（因为单程飞过去不用回来，送完货就地找充电桩，不考虑返程）。
2. 卸货损耗：在目标地点降落并卸货需要额外消耗 $w_i$ 点电量。

完成第 $i$ 个订单能获得 $val_i$ 元的配送费。由于无人机电池技术的限制，它今天一天出发的总电量上限为 $B$。

请问在不把电池耗尽的前提下，最多能赚多少钱？（每个订单只能接一次）。

输入格式

第一行四个整数 $V, E, K, B$，分别表示路口数、道路数、订单数和电池总容量。

接下来 $E$ 行，每行三个整数 $u, v, d$，表示路口 $u$ 和 $v$ 之间有一条距离为 $d$ 的道路。

接下来 $K$ 行，每行三个整数 $target_i, w_i, val_i$，分别表示第 $i$ 个订单的目的地、卸货耗电、配送费。

输出格式

输出一个整数，表示最大配送费。

样例输入

4 4 3 20
1 2 2
2 3 3
1 3 6
3 4 4
2 5 10
3 2 15
4 1 20

样例输出

35

数据范围

• $1 \le V \le 1000$
• $1 \le E \le 5000$
• $1 \le K \le 500$
• $1 \le B \le 50000$
• 路口编号 $1 \sim V$，保证图连通