Cartesianism
The state of Xivshchyna consists of N_x cities, with some pairs connected by two-way roads, each having a specific length. There are M_x intercity roads in total, and it is possible to travel between any two cities using these roads. The cities are numbered from 1 to N_x.
Similarly, the state of Igrekivshchyna has N_y cities, with some pairs connected by two-way roads, each with its own length. There are M_y intercity roads in total, and one can travel between any two cities using these roads. The cities are numbered from 1 to N_y.
The state of Dekartivshchyna comprises N = N_x ∙ N_y cities. Each city in Dekartivshchyna corresponds uniquely to a pair of cities (x,y), where x is a city in Xivshchyna, and y is a city in Igrekivshchyna. Some pairs of cities in Dekartivshchyna are connected by two-way roads. There are exactly M = N_x ∙ M_y + N_y ∙ M_x roads in total. A road between cities (x_1,y_1) and (x_2,y_2) exists under one of the following conditions:
If x_1=x_2, and there is a road between cities y_1 and y_2 in Igrekivshchyna. In this case, the road length between cities (x,y_1) and (x,y_2) in Dekartivshchyna is the same as the road length between cities y_1 and y_2 in Igrekivshchyna.
If y_1=y_2, and there is a road between cities x_1 and x_2 in Xivshchyna. In this case, the road length between cities (x_1,y) and (x_2,y) in Dekartivshchyna is the same as the road length between cities x_1 and x_2 in Xivshchyna.
Cities from different states are not connected by roads.
Task
This problem consists of two subtasks. In both, all road connection information is provided in the input data.
In the first subtask, determine the shortest path length by roads in Dekartivshchyna from city (1,1) to city (N_x,N_y).
In the second subtask, some roads in Dekartivshchyna need to be closed. Your task is to identify which roads of the smallest total length can remain in Dekartivshchyna so that it is still possible to travel between any two cities.
Write a program named cartesius to solve these subtasks.
Input
The first line of the input file cartesius.dat contains the subtask number to be solved (1 or 2). The second line contains natural numbers N_x and M_x (1≤N_x≤5•10^4, 1≤M_x≤5•10^4) — the number of cities and roads in Xivshchyna. The next M_x lines describe the roads in Xivshchyna: each line contains three numbers, where the first two specify the numbers of different cities connected by a road, and the third is the road's length (a natural number not exceeding 10^7).
The next line of the input file specifies natural numbers N_y and M_y (1≤N_y≤5•10^4, 1≤M_y≤5•10^4) — the number of cities and roads in Igrekivshchyna. The next M_y lines describe the roads in Igrekivshchyna; the data format and constraints are the same as those described above.
Output
The output file cartesius.sol should contain a single integer — the answer to the subtask question.
Examples
Scoring
The test set consists of 4 blocks, with the following additional conditions:
12 points: subtask number — 1, none of the numbers N_x, M_x, N_y, M_y exceed 200.
28 points: subtask number — 1, no additional constraints.
12 points: subtask number — 2, none of the numbers N_x, M_x, N_y, M_y exceed 200.
48 points: subtask number — 2, no additional constraints.