题目描述

国家 Xikovo 由 Nx 个城市组成，其中有一些城市对之间由双向直达公路连接。每条直达公路都有一个长度。这样的直达公路共有 Mx 条，并且已知在 Xikovo 中任意两个城市之间都存在一条由这些直达公路构成的路径。Xikovo 的城市编号为 1 到 Nx。

国家 Igrekovo 由 Ny 个城市组成，其中有一些城市对之间由双向直达公路连接。每条直达公路也都有一个长度。这样的直达公路共有 My 条，并且已知在 Igrekovo 中任意两个城市之间都存在一条由这些直达公路构成的路径。Igrekovo 的城市编号为 1 到 Ny。

国家 Decartovo 由 N = Nx · Ny 个城市组成：Decartovo 中的每个城市都可以与一个二元组 (x, y) 一一对应，其中 x 是 Xikovo 中的一个城市，y 是 Igrekovo 中的一个城市。

Decartovo 中的一些城市对之间也有双向直达公路，并满足：

• Decartovo 中的直达公路总数恰好为 M = Nx · My + Ny · Mx；
• 对应二元组 (x1, y1) 和 (x2, y2) 的两个城市之间存在直达公路，当且仅当以下两种情况之一成立：

1. x1 = x2 = x，并且在 Igrekovo 中城市 y1 与 y2 之间有直达公路。
   此时，Decartovo 中对应 (x, y1) 与 (x, y2) 的两座城市之间的公路长度，等于 Igrekovo 中 y1 与 y2 之间公路的长度。
2. y1 = y2 = y，并且在 Xikovo 中城市 x1 与 x2 之间有直达公路。
   此时，Decartovo 中对应 (x1, y) 与 (x2, y) 的两座城市之间的公路长度，等于 Xikovo 中 x1 与 x2 之间公路的长度。

不同国家之间没有公路连接。

请编写程序 cartesius，解决下面两个任务之一：

1. 求 Decartovo 中对应 (1, 1) 与 (Nx, Ny) 的两座城市之间最短路径的长度；
2. 需要关闭 Decartovo 中的一些直达公路。你的程序要找出最小的公路总长度，使得保留下来的公路仍然能保证任意两座城市之间至少存在一条路径。

输入格式

第一行一个整数，表示需要解决的任务编号（1 或 2）。

第二行两个正整数 Nx 和 Mx，表示 Xikovo 中城市数和直达公路数。
接下来 Mx 行，每行三个正整数，前两个表示这条公路连接的两个城市编号，第三个表示这条公路的长度。

接下来一行两个正整数 Ny 和 My，表示 Igrekovo 中城市数和直达公路数。
接下来 My 行，每行三个正整数，前两个表示这条公路连接的两个城市编号，第三个表示这条公路的长度。

输出格式

输出一行一个整数，表示对应任务的答案。

数据范围

• 1 ≤ Nx ≤ 5 × 10^4
• 1 ≤ Mx ≤ 5 × 10^4
• 1 ≤ Ny ≤ 5 × 10^4
• 1 ≤ My ≤ 5 × 10^4
• 1 ≤ 公路长度 ≤ 10^7

样例 1

输入

1
3 2
2 1 15
3 1 14
3 2
2 1 15
3 2 15

输出

44

样例 2

输入

2
3 2
2 1 15
3 1 14
3 2
2 1 15
3 2 15

输出

117

子任务与评分

1. 子任务 1（12 分）：任务编号为 1，并且 Nx, Mx, Ny, My 都不超过 200。
2. 子任务 2（28 分）：任务编号为 1，无额外限制。
3. 子任务 3（12 分）：任务编号为 2，并且 Nx, Mx, Ny, My 都不超过 200。
4. 子任务 4（48 分）：任务编号为 2，无额外限制。

只有通过某个子任务中的全部测试点，才能获得该子任务的分数。