28599번 - Производство Мерцания 다국어

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

Город представляет собой взвешенный неориентированный граф из $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$ компонентов.