B. Производство Мерцания
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Примеры
Входные данные
3 3 2
1 2 5
1 3 2
3 2 2
3
1 15 1
2 1 1
3 3 2
10
Выходные данные
15
Входные данные
4 4 4
4 2 5
1 3 3
3 4 16
2 1 9
10
3 18 8
1 2 12
4 8 19
2 9 15
2 12 2
4 20 4
3 11 14
2 5 3
4 19 1
1 1 20
3
Выходные данные
26