Задача G. Грузоперевозки

Автор:Р. Данилов   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Стивен устроился на работу программистом в новую транспортную компанию. В его обязанности входит оптимизация стоимости грузоперевозок из одной страны в другую.

В базе данных компании содержатся N городов, пронумерованных от 1 до N, и M односторонних дорог между некоторыми из них. Дорога номер i характеризуется тремя числами ui vi li — начальным городом, конечным городом и длиной дороги. Гарантируется, что ui ≠ vi, и не существует двух разных дорог i, j, для которых ui = uj, vi = vj.

Страна представляет из себя такое множество из одного или более городов, что:

  1. из каждого города страны можно добраться в любой другой город этой страны по дорогам;
  2. ко множеству нельзя добавить ни одного города, сохранив при этом свойство 1.

Так как страны не дружат между собой, дороги из одной страны в другую находятся в плачевном состоянии. Это представляет главную проблему, поэтому стоимость перевозок внутри страны можно считать равной нулю. Стоимостью перевозки груза по дороге, соединяющей города из разных стран, будем считать длину этой дороги.

Запрос на перевозку определяется парой чисел sj fj — номерами города отправления и города назначения j-го груза. Напишите программу, которая для каждого из Q запросов определяет наименьшую возможную стоимость перевозки груза.

В тесте из примера имеется две страны. Одна состоит из городов 1, 2, 3, другая — из городов 4, 5.

Формат входного файла

Входной файл содержит целые числа N M — количество городов и дорог соответственно.

Далее следует M троек целых чисел ui vi li — начальный город, конечный город и длина i-й дороги.

Далее следует целое число Q, за котором идут Q запросов по два целых числа sj fj — город отправления и город назначения j-го груза.

Формат выходного файла

Выходной файл должен содержать Q целых чисел, каждое из которых равно наименьшей стоимости перевозки для соответствующего запроса, или  − 1, если эта перевозка невозможна.

Ограничения

1 ≤ N ≤ 300; 0 ≤ M ≤ N(N − 1); 1 ≤ Q ≤ 105; 1 ≤ ui, vi, sj, fj ≤ N; 0 ≤ li ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 6
1 2 1
2 3 3
3 1 3
1 4 2
4 5 1
5 4 2
4
2 5
1 3
4 1
1 1
2
0
-1
0

0.092s 0.026s 13