메르차니예 생산

Silco가 Мерцание를 합성하려면 특수한 기계가 필요합니다. 기계를 쓰기 전에 도시에서 기계를 구해 공장으로 옮겨야 합니다.

도시는 정점이 $n$개, 간선이 $m$개인 가중치 무방향 그래프입니다. 공장은 1번 정점에 있습니다. 일부 정점에는 기계가 있습니다. $i$번째 기계는 세 수 $(v_i, h_i, t_i)$로 표현됩니다. $v_i$는 기계가 있는 정점 번호이고, $h_i$는 기계를 설치하고 예열하는 데 걸리는 시간이며, $t_i$는 기계가 성분을 만드는 속도입니다.

Silco에게는 $k$명의 자유 택배원이 있습니다. 각 택배원은 기계를 한 대만 옮길 수 있습니다. 기계를 옮긴 택배원은 몸을 숨기므로 다른 기계를 가지러 갈 수 없습니다. 따라서 Silco는 최대 $k$대의 기계를 공장으로 옮길 수 있습니다.

모든 택배원은 시각 0에 공장에서 동시에 출발합니다. 기계가 있는 정점까지 가는 데 걸리는 시간은 그 정점까지의 최단 경로에 있는 간선 가중치의 합입니다. 기계가 1번 정점에 있으면 옮기는 데 시간은 들지 않지만, 어떤 경우든 택배원 한 명이 필요합니다.

기계가 공장에 도착하면 먼저 $h_i$ 단위 시간 동안 준비합니다. 그 뒤로는 $t_i$ 단위 시간마다 성분을 하나씩 계속 만듭니다. 성분 $V$개를 만드는 데 필요한 최소 시간은 얼마입니까?

첫 줄에 정수 $n$, $m$, $k$가 공백으로 구분되어 주어집니다. 각각 정점의 수, 간선의 수, 택배원의 수입니다 ($2 \leq n, m, k \leq 2 \cdot 10^5$).

이어지는 $m$개의 줄에는 정수 $a_i$, $b_i$, $c_i$가 주어집니다. 정점 $a_i$와 $b_i$를 잇는 가중치 $c_i$의 간선이 있다는 뜻입니다 ($1 \leq a_i, b_i \leq n$; $a_i \neq b_i$; $1 \leq c_i \leq 10^9$). 주어지는 간선은 모두 서로 다릅니다.

다음 줄에는 도시에 있는 기계의 수 $s$가 주어집니다 ($1 \leq s \leq 2 \cdot 10^5$).

이어지는 $s$개의 줄에는 기계를 나타내는 세 정수 $v_i$, $h_i$, $t_i$가 주어집니다. 기계가 있는 정점, 예열 시간, 성분 하나를 만드는 데 걸리는 시간입니다 ($1 \leq v_i \leq n$; $1 \leq h_i, t_i \leq 10^9$).

마지막 줄에는 만들어야 하는 성분의 수 $V$가 주어집니다 ($1 \leq V \leq 10^9$).

성분 $V$개를 만드는 데 필요한 최소 시간을 정수 하나로 출력합니다.