Производство Мерцания

Чтобы синтезировать Мерцание, Силко необходимы специальные станки. Но перед тем, как их использовать, станки нужно раздобыть в городе и доставить на фабрику.

Город представляет собой взвешенный неориентированный граф из $n$ вершин и $m$ ребер, фабрика находится в вершине с номером $1$. В некоторых вершинах находятся станки, $i$-й из которых характеризуется тройкой чисел $(v\_i, h\_i, t\_i)$. Здесь $v\_i$ --- номер вершины графа, в которой он находится, $h\_i$ --- время, необходимое на установку и разогрев станка, и $t\_i$ --- скорость производства компонентов Мерцания.

У Силко есть $k$ свободных курьеров, каждый из которых может привезти один станок. Доставивший один станок курьер должен залечь на дно, и больше за станками отправиться не может. Таким образом, всего Силко может доставить на фабрику не более $k$ станков.

Все курьеры начинают одновременно в момент времени $0$, находясь на фабрике. Чтобы добраться до станка, курьеру нужно потратить время, равное сумме весов ребер на кратчайшем пути до вершины, в которой станок находится. Если станок находится в вершине $1$, на его доставку не требуется время, однако в любом случае потребуется один курьер.

Когда станок прибывает на фабрику, сначала тратится $h\_i$ единиц времени на его подготовку, после чего он начинает непрерывно производить один компонент в $t\_i$ единиц времени. Какое минимальное время нужно для производства $V$ компонентов?

В первой строке ввода через пробел перечислены три целых числа $n$, $m$ и $k$ --- количество вершин графа, ребер графа и курьеров, соответственно ($2 \leqslant n, m, k \leqslant 2 \cdot 10^5$).

В $i$-й из следующих $m$ строк через пробел даны три целых числа $a\_i$, $b\_i$ и $c\_i$, означающие, что между вершинами $a\_i$ и $b\_i$ проведено ребро веса $c\_i$ ($1 \leqslant a\_i, b\_i \leqslant n$; $a\_i \neq b\_i$; $1 \leqslant c\_i \leqslant 10^9$). Гарантируется, что все перечисленные ребра различны.

В следующей строке дано единственное целое число $s$ --- количество станков, расположенных в городе ($1 \leqslant s \leqslant 2 \cdot 10^5$).

В $i$-й из следующих $s$ строк дано описание $i$-го станка, состоящее из трех целых чисел $v\_i$, $h\_i$ и $t\_i$ --- вершины, в которой расположен станок, времени его разогрева и времени производства станком одного компонента, соответственно ($1 \leqslant v\_i \leqslant n$; $1 \leqslant h\_i, t\_i \leqslant 10^9$).

В последней строке дано единственное целое число $V$ --- количество компонентов, которые необходимо произвести ($1 \leqslant V \leqslant 10^9$).

Выведите единственное целое число --- ответ на задачу --- минимальное время, необходимое для производства $V$ компонентов.