Декартівщина

Держава Іксівщина складається з 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, додаткових обмежень немає.