C. Каналы связи

Ограничение времени 2 секунды
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Сеть провайдера состоит из N узлов и M оптоволоконных линий связи между парами узлов. Передача данных по оптоволоконной линии может осуществляться в обе стороны. Любые два узла соединены не более чем одной оптоволоконой линией. Для каждой оптоволоконной линии известно время прохождения сигнала по ней, измеряемое в наносекундах.
Инженеры провайдера подготовили K предложений о прокладке новых оптоволоконных линий, каждое предложение имеет вид «строительство линии от узла U до узла V со временем прохождения сигнала T будет стоить C бурлей». При этом если узлы U и V уже были соединены в исходной сети, то предложений о строительстве новой линии между ними гарантированно не было подготовлено.
В связи с развитием облачного гейминга возросли требования к скорости прохождения сигнала от узлов, рядом с которыми размещены сервера до мест скопления геймеров. В частности, было сформировано P требований вида «время прохождения сигнала от узла A до узла B не должно превосходить T наносекунд».
Определите, какие из предложений о строительстве нужно удовлетворить, чтобы выполнялись все требования. Акционеры провайдера расстраиваются от строительства дорогих оптоволоконных линий, поэтому необходимо минимизировать стоимость самой дорогой новой оптоволоконной линии.
Формат ввода
В первой строке записаны числа N (1 ? N ? 100) и m (0 ? M ? 10?000) — количество узлов и уже существующий оптоволоконных линий.
Следующие M строк содержат описание оптоволоконных линий. Каждое описание состоит из трех целых чисел U, V, T (1 ? U, V ? N, U ? V, 1 ? T ? 10?000) — номеров соединяемых линией узлов и времени прохождения сигнала в наносекундах.
В следующей строке записано число K (1 ? K ? 10?000) — количество предложений о строительстве новых линий.
Следующие K строк содержат описание предложений. Каждое описание состоит из четырех целых чисел U, V, T и C (1 ? U, V ? N, U ? V, 1 ? T ? 10?000, 1 ? C ? 109) — номера соединяемых узлов, время прохождения сигнала и стоимость постройки линии соответственно.
В следующей строке записано число P (1 ? P ? 1000) — количество требований.
Следующие P строк содержат описание требований. Каждое описание состоит из трех целых чисел A, B и T (1 ? A, B ? N, A ? B, 1 ? T ? 108) — номера узлов и максимально допустимое время прохождения сигнала между ними.
Формат вывода
Выведите количество предложений о строительстве, которые необходимо удовлетворить.
В следующей строке выведите номера предложений, которые необходимо удовлетворить, в порядке возрастания. Предложения нумеруются как во входных данных начиная с единицы. Минимизурйте стоимость строительства самой дорогой построенной предложенной линии.
Если удовлетворить требования невозможно, выведите одно число -1.
Если все требования удовлетворены без строительства новых линий, выведите одно число 0.
Пример 1
Ввод
3 0
3
2 3 2 1
1 2 2 1
1 3 1 3
1
1 3 4
Вывод
2
1 2
Пример 2
Ввод
3 1
1 2 2
2
1 3 1 3
2 3 2 1
1
1 3 3
Вывод
2
1 2