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