데카르트 곱 최소 신장 트리

가중 무향 단순 그래프 $G$와 $H$가 주어진다. 두 그래프의 데카르트 곱 $G \square H$는 정점 집합이 두 그래프 정점 집합의 데카르트 곱 $V(G) \times V(H)$이고, 정점 $(u_1, v_1)$과 $(u_2, v_2)$ 사이에 다음 조건을 만족할 때에만 간선이 있는 그래프로 정의한다.

• $v_1 = v_2$이고 $G$에 간선 $(u_1, u_2)$가 있다. 이때 $G \square H$의 간선 $((u_1, v_1), (u_2, v_2))$의 가중치는 $G$의 간선 $(u_1, u_2)$와 같다.
• 또는 $u_1 = u_2$이고 $H$에 간선 $(v_1, v_2)$가 있다. 이때 $G \square H$의 간선 $((u_1, v_1), (u_2, v_2))$의 가중치는 $H$의 간선 $(v_1, v_2)$와 같다.

연결 그래프 $G$와 $H$가 주어질 때, $G \square H$의 최소 신장 트리의 총 가중치를 구하여라.

첫째 줄에 네 정수 $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$). 각각 $G$의 정점 수, $G$의 간선 수, $H$의 정점 수, $H$의 간선 수이다.

다음 $m_1$개 줄에는 세 정수 $u_i, v_i, w_i$가 주어진다($0 \leq u_i, v_i \leq n_1 - 1$; $1 \leq w_i \leq 10^8$). $G$에서 정점 $u_i$와 $v_i$를 잇는 가중치 $w_i$의 간선을 나타낸다.

다음 $m_2$개 줄에는 세 정수 $u_i, v_i, w_i$가 주어진다($0 \leq u_i, v_i \leq n_2 - 1$; $1 \leq w_i \leq 10^8$). $H$에서 정점 $u_i$와 $v_i$를 잇는 가중치 $w_i$의 간선을 나타낸다.

그래프 $G$와 $H$는 단순하고 연결되어 있음이 보장된다. 그래프가 단순하다는 것은 자기 자신으로 향하는 간선이 없고, 두 정점 사이에 간선이 많아야 하나 존재한다는 뜻이다.

$G \square H$의 최소 신장 트리의 가중치를 정수 하나로 출력한다.