Shimmer Production

Silco needs special machines to synthesize Shimmer. Before using them, the machines must be obtained in the city and delivered to the factory.

The city is a weighted undirected graph with $n$ vertices and $m$ edges. The factory is at vertex $1$. Some vertices contain machines. The $i$-th machine is described by a triple $(v_i, h_i, t_i)$, where $v_i$ is the vertex the machine is in, $h_i$ is the time needed to install and warm up the machine, and $t_i$ is the rate at which the machine produces Shimmer components.

Silco has $k$ free couriers. Each courier can bring one machine. A courier who has delivered a machine must lie low and cannot go for more machines. So Silco can deliver at most $k$ machines to the factory.

All couriers start at the factory at time $0$. To reach a machine, a courier needs time equal to the sum of edge weights on the shortest path to the vertex containing that machine. If a machine is in vertex $1$, delivering it takes no time, but it still requires one courier.

When a machine arrives at the factory, it first spends $h_i$ time units on preparation, after which it produces one component every $t_i$ time units. What is the minimum time needed to produce $V$ components?

The first line contains three integers $n$, $m$, and $k$, the number of vertices, the number of edges, and the number of couriers ($2 \leq n, m, k \leq 2 \cdot 10^5$).

The next $m$ lines each contain three integers $a_i$, $b_i$, and $c_i$, meaning that an edge of weight $c_i$ connects vertices $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$; $a_i \neq b_i$; $1 \leq c_i \leq 10^9$). All listed edges are distinct.

The next line contains a single integer $s$, the number of machines in the city ($1 \leq s \leq 2 \cdot 10^5$).

Each of the next $s$ lines describes one machine with three integers $v_i$, $h_i$, and $t_i$: the vertex containing the machine, its warm-up time, and the time it takes to produce one component ($1 \leq v_i \leq n$; $1 \leq h_i, t_i \leq 10^9$).

The last line contains a single integer $V$, the number of components to produce ($1 \leq V \leq 10^9$).

Print a single integer, the minimum time needed to produce $V$ components.