Декартово

Государство Иксово состоит из N_x городов, некоторые пары которых связаны дорогами с двусторонним движением. Каждая дорога имеет свою длину. Всего межгородских дорог в стране M_x, при чем известно, что из каждого города Иксевщины можно доехать по дорогам до каждого другого города этой страны. Города Иксово пронуменрованы натуральными числами от 1 до N_x.

Государство Игреково состоит из N_y городов, некоторые пары которых связаны дорогами с двусторонним движением. Каждая дорога имеет свою длину. Всего межгородских дорог в стране M_y, при чем известно, что из каждого города Игреково можно доехать по дорогам до каждого другого города этой страны. Города Игреково пронуменрованы натуральными числами от 1 до N_y.

Страна Декартово состоит из N=N_x∙N_y_{ }городов: каждому городу Декартово во взаимно однозначное соответствие можно поставить пару городов-побратимов (x,y), где x — город Иксово, а y — город Игреково. Некоторые пары городов Декартово также соединены дорогами с двусторонним движением. Дорог в стране ровноM=N_x∙M_y+N_y∙M_x. При этом дорога между городами (x_1,y_1) и (x_2,y_2) существует только в одном из таких двух случаев:

1. Если x_1=x_2, а между городами y_1 и y_2 Игреково проложена дорога. При этом длина дороги между городами(x,y_1) и (x,y_2) Декартово равно длине дороги между городами y_1 и y_2 Игреково.

2. Если y_1=y_2, а между городами x_1 и x_{2 }Иксевщены проложена дорога. При этом длина дороги между городами (x_1,y) и (x_2,y) Декартово равно длине дороги между городами x_1 и x_2 Иксево.

Города разных государств между собой дорогами не соединены.

Задание

Данная задача состоит из двух подзадач. В обеих подзадачах всю информацию про соединение дорогами задано во входных файлах.

1. В первой подзадаче требуется определить длину самого короткого пути по дорогам Декартовщины из города (1,1) в город (N_x,N_y).

2. Во второй подзадаче некоторые дороги Декартовщины требуется закрыть. Ваша задача — определить, дороги какой наименьшей суммарной длины можно оставить в Декартовщине, чтобы из любого ее города все еще можно было попасть в любой другой.

Напишите программу cartesius, которая решает эти подзадачи.

Входные данные

Первая строка входного файла cartesius.dat содержит номер подзадачи, которую требуется решить (1 или 2). Вторая строка содержит натуральные числа N_x и M_x (1≤N_x≤5•10^4, 1≤M_x≤5•10^4) — количество городов и дорог в Иксово. В последующих M_x строках описаны дороги Иксово: в каждой строке по три числа, где первые два задают номера разных городов, соедененных дорогой, а третья есть длиной соответствующей дороги (натуральное число, которое не превышает 10^7).

В следующей строке входного файла указаны натуральные числа N_y и M_y (1≤N_y≤5•10^4, 1≤M_y≤5•10^4) — количество городов и дорог в Игреково. Последующие M_y строк содержат описание дорог Игреково; формат данных и ограничения соответствуют описанным выше.

Выходные данные

Выходной файл cartesius.sol должен содержать единственно целое число — ответ на вопрос подзадачи.

Примеры

Оценивание

Набор тестов состоит из 4 блоков, для которых дополнительно выполняются такие условия:

1. 12 баллов: номер подзадачи — 1, числа N_x, M_x, N_y, M_y не превышают 200.

2. 28 баллов: номер подзадачи — 1, дополнительных ограничений нет.

3. 12 баллов: номер подзадачи — 2, числа N_x, M_x, N_y, M_y не превышают 200.

4. 48 баллов: номер подзадачи — 2, дополнительных ограничений нет.