408327: GYM103098 C Cartesian MST

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$$$.

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

15