Государство Иксово состоит из \textit{\textbf{N_x}} городов, некоторые пары которых связаны дорогами с двусторонним движением. Каждая дорога имеет свою длину. Всего межгородских дорог в стране \textit{\textbf{M}}\textbf{_x}, при чем известно, что из каждого города Иксевщины можно доехать по дорогам до каждого другого города этой страны. Города Иксово пронуменрованы натуральными числами от \textbf{1} до \textit{\textbf{N_x}}. Государство Игреково состоит из \textit{\textbf{N_y}} городов, некоторые пары которых связаны дорогами с двусторонним движением. Каждая дорога имеет свою длину. Всего межгородских дорог в стране \textit{M}_y, при чем известно, что из каждого города Игреково можно доехать по дорогам до каждого другого города этой страны. Города Игреково пронуменрованы натуральными числами от \textbf{1} до \textit{\textbf{N_y}}. Страна Декартово состоит из\textbf{ }\textit{\textbf{N}}\textbf{=}\textit{\textbf{N_x}}\textbf{∙}\textit{\textbf{N_y}}\textit{_\{ \}}городов: каждому городу Декартово во взаимно однозначное соответствие можно поставить пару городов-побратимов\textit{ }\textit{\textbf{(x,y)}}, где \textit{\textbf{x}} --- город Иксово, а \textit{\textbf{y}}\textit{ }--- город Игреково. Некоторые пары городов Декартово также соединены дорогами с двусторонним движением. Дорог в стране ровно\textit{\textbf{M}}\textbf{=}\textit{\textbf{N_x}}\textbf{∙}\textit{\textbf{M_y}}\textbf{+}\textit{\textbf{N_y}}\textbf{∙}\textit{\textbf{M_x}}. При этом дорога между городами \textbf{(}\textit{\textbf{x}}\textbf{_1,}\textit{\textbf{y}}\textbf{_1)} и \textbf{(}\textit{\textbf{x}}\textbf{_2,}\textit{\textbf{y}}\textbf{_2)} существует только в одном из таких двух случаев: \begin{enumerate} \item Если \textit{\textbf{x}}\textbf{_1=}\textit{\textbf{x}}\textbf{_2}, а между городами \textit{\textbf{y}}\textbf{_1} и \textit{\textbf{y}}\textbf{_2} Игреково проложена дорога. При этом длина дороги между городами\textbf{(}\textit{\textbf{x}}\textbf{,}\textit{\textbf{y}}\textbf{_1)} и \textbf{(}\textit{\textbf{x}}\textbf{,}\textit{\textbf{y}}\textbf{_2)} Декартово равно длине дороги между городами \textit{\textbf{y}}\textbf{_1} и \textit{\textbf{y}}\textbf{_2} Игреково. \item Если \textit{\textbf{y}}\textbf{_1=}\textit{\textbf{y}}\textbf{_2}, а между городами\textit{ }\textit{\textbf{x}}\textbf{_1} и \textit{\textbf{x}}_\{2 \}Иксевщены проложена дорога. При этом длина дороги между городами \textbf{(}\textit{\textbf{x}}\textbf{_1,}\textit{\textbf{y}}\textbf{)} и \textbf{(}\textit{\textbf{x}}\textbf{_2,}\textit{\textbf{y}}\textbf{)} Декартово равно длине дороги между городами \textit{\textbf{x}}\textbf{_1} и \textit{\textbf{x}}\textbf{_2} Иксево. \end{enumerate} Города разных государств между собой дорогами не соединены. \textbf{Задание} Данная задача состоит из двух подзадач. В обеих подзадачах всю информацию про соединение дорогами задано во входных файлах. \begin{enumerate} \item В первой подзадаче требуется определить длину самого короткого пути по дорогам Декартовщины из города (1,1) в город (\textit{N_x},\textit{N_y}). \item Во второй подзадаче некоторые дороги Декартовщины требуется закрыть. Ваша задача --- определить, дороги какой наименьшей суммарной длины можно оставить в Декартовщине, чтобы из любого ее города все еще можно было попасть в любой другой. \end{enumerate} Напишите программу, которая решает эти подзадачи. \InputFile Первая строка входного файла cartesius.dat содержит номер подзадачи, которую требуется решить (1 или 2). Вторая строка содержит натуральные числа \textit{\textbf{N_x}} и \textit{\textbf{M_x}} \textbf{(1≤}\textit{\textbf{N_x}}\textbf{≤5•10^4, 1≤}\textit{\textbf{M_x}}\textbf{≤5•10^4)} --- количество городов и дорог в Иксово. В последующих \textit{\textbf{M_x}} строках описаны дороги Иксово: в каждой строке по три числа, где первые два задают номера разных городов, соедененных дорогой, а третья есть длиной соответствующей дороги (натуральное число, которое не превышает \textbf{10^7}). В следующей строке входного файла указаны натуральные числа \textit{\textbf{N_y}} и \textit{\textbf{M_y}} \textbf{(1≤}\textit{\textbf{N_y}}\textbf{≤5•10^4, 1≤}\textit{\textbf{M_y}}\textbf{≤5•10^4)} --- количество городов и дорог в Игреково. Последующие \textit{\textbf{M_y}} строк содержат описание дорог Игреково; формат данных и ограничения соответствуют описанным выше. \OutputFile Выходной файл cartesius.sol должен содержать единственно целое число --- ответ на вопрос подзадачи. \Scoring Набор тестов состоит из 4 блоков, для которых дополнительно выполняются такие условия: \begin{enumerate} \item 12 баллов: номер подзадачи --- 1, числа \textit{N_x}, \textit{M_x}, \textit{N_y}, \textit{M_y} не превышают 200. \item 28 баллов: номер подзадачи --- 1, дополнительных ограничений нет. \item 12 баллов: номер подзадачи --- 2, числа \textit{N_x}, \textit{M_x}, \textit{N_y}, \textit{M_y} не превышают 200. \item 48 баллов: номер подзадачи --- 2, дополнительных ограничений нет. \end{enumerate}