Держава Іксівщина складається з \textit{\textbf{N_x}} міст, деякі пари яких сполучено дорогами з двостороннім рухом. Кожна дорога має свою довжину. Усього міжміських доріг у державі \textit{\textbf{M}}\textbf{_x}, причому відомо, що з кожного міста Іксівщини можна доїхати по дорогах до кожного іншого міста цієї держави. Міста Іксівщини занумеровано натуральними числами від \textbf{1} до \textit{\textbf{N_x}}. Держава Ігреківщина складається з \textit{\textbf{N_y}} міст, деякі пари яких також сполучено дорогами з двостороннім рухом. Кожна дорога має свою довжину. Усього міжміських доріг у державі \textit{\textbf{M_y}}\textbf{,} причому відомо, що з кожного міста Ігреківщини можна доїхати по дорогах до кожного іншого міста цієї держави. Міста Ігреківщини занумеровано натуральними числами від 1 до \textit{\textbf{N_y}}. Держава Декартівщина складається з \textit{\textbf{N}}\textbf{=}\textit{\textbf{N_x}}\textbf{∙}\textit{\textbf{N_y}}\textbf{ }міст: кожному місту Декартівщини у взаємно однозначну відповідність можна поставити пару міст-побратимів \textit{\textbf{(x,y)}}\textbf{,} де \textit{x} --- місто Іксівщини, а \textit{\textbf{y}} --- місто Ігреківщини. Деякі пари міст Декартівщини також сполучено дорогами з двостороннім рухом. Доріг у державі рівно \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{\textbf{x}}\textbf{_1} та \textit{\textbf{x}}\textbf{_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 У першій підзадачі потрібно визначити довжину найкоротшого шляху дорогами Декартівщини з міста \textbf{(1,1)} у місто \textbf{(}\textit{\textbf{N_x}}\textbf{,}\textit{\textbf{N_y}}\textbf{)}. \item У другій підзадачі деякі дороги Декартівщини потрібно закрити. Ваша задача --- визначити, дороги якої найменшої сумарної довжини можна залишити в Декартівщині, щоб із будь-якого її міста досі можна було потрапити в будь-яке інше. \end{enumerate} Напишіть програму cartesius, що розв’язує ці підзадачі. \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}