시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB31212080.000%

문제

Let $G$ and $H$ be two weighted undirected simple graphs. We define the cartesian product of the two graphs, $G \square H$, as the graph whose vertex set is the cartesian set product of the vertex sets of the two graphs $V(G) \times V(H)$ and in which there is an edge between vertices $(u_1, v_1)$ and $(u_2, v_2)$ if and only if:

  • $v_1 = v_2$ and there is an edge $(u_1, u_2)$ in $G$. In this case, the edge$((u_1, v_1), (u_2, v_2))$ in $G \square H$ has the same weight as the edge $(u_1, u_2)$ in $G$.
  • or $u_1 = u_2$ and there is an edge $(v_1, v_2)$ in $H$. In this case, the edge$((u_1, v_1), (u_2, v_2))$ in $G \square H$ has the same weight as the edge $(v_1, v_2)$ in $H$.

You are given two connected graphs $G$ and $H$. Compute the total weight of the minimum spanning tree of $G \square H$.

입력

The first line contains four integers $n_1, m_1, n_2, m_2$ ($2 \leq n_1, n_2 \leq 10^5$; $1 \leq m_1, m_2 \leq 10^5$): the number of vertices of $G$, the number of edges of $G$, the number of vertices of $H$, and the number of edges of $H$, respectively. 

Each of the next $m_1$ lines contains three integers $u_i, v_i, w_i$ ($0 \leq u_i, v_i \leq n_1 - 1$; $1 \leq w_i \leq 10^8$), describing an edge of $G$ between vertices $u_i$ and $v_i$ with weight $w_i$.

Each of the next $m_2$ lines contains three integers $u_i, v_i, w_i$ ($0 \leq u_i, v_i \leq n_2 - 1$; $1 \leq w_i \leq 10^8$), describing an edge of $H$ between vertices $u_i$ and $v_i$ with weight $w_i$.

It is guaranteed that graphs $G$ and $H$ are simple and connected. Recall that a graph is simple if there are no edges between a vertex and itself, and there is at most one edge between any two vertices.

출력

Output one integer: the weight of the minimum spanning tree of $G \square H$.

예제 입력 1

4 4 3 2
0 1 3
1 2 2
2 3 2
3 0 5
0 1 1
1 2 1

예제 출력 1

15