Міське водіння#3377
Ви нещодавно почали часто відвідувати Сан-Франциско у свій вільний час і зрозуміли, що водіння в місті є великою проблемою. Проте вас цікавлять лише місць у місті, і ви вирішили спробувати покращити свій досвід водіння. Оскільки у вас немає GPS і ви не можете запам'ятати занадто багато різних маршрутів, ви записали напрямки та скільки часу займає дістатися між різними парами місць (однаково в обох напрямках), забезпечуючи, що, використовуючи лише ці шляхи, ви можете дістатися з будь-якого місця до будь-якого іншого.
Тепер ви плануєте свою поїздку на вихідні і вам потрібно визначити найшвидший спосіб дістатися між парами місць у місті, використовуючи лише маршрути, які ви записали.
Вхід складається з декількох тестових випадків. Перший рядок містить одне ціле число (3 \leq N \leq 100000) — кількість цікавих місць і одночасно кількість записаних маршрутів. Наступні рядків містять по три цілих числа , та (0 \leq u, v < N, 1 \leq w \leq 1000) — є маршрут від місця до місця і назад (шляхи двосторонні), який займає часу. Далі йде рядок з одним цілим числом (1 \leq Q \leq 10000) — кількість пар місць, для яких треба знайти найкоротший маршрут. Далі рядків, кожен містить два цілих числа та (0 \leq u, v < N) — потрібно знайти мінімальний час, щоб дістатися з місця до місця . Вхід закінчується рядком N = 0.
Для кожного тестового випадку виведіть рядків, для кожної пари місць та , для яких потрібно знайти мінімальний час. Кожен рядок повинен містити одне число — мінімальний час, необхідний для поїздки з місця до місця .
Приклад 1