В городе A планируется модернизация автобусной сети. В городе N остановок, соединённых дорогами. Каждая дорога соединяет ровно две остановки и имеет протяжённость (в километрах). Автобусы могут двигаться по дорогам в обоих направлениях.
Городская администрация хочет построить K новых автобусных маршрутов. Каждый маршрут должен представлять собой путь от одной остановки до другой (остановки на маршруте могут повторяться, но предпочтительно минимизировать дублирование). Все маршруты должны начинаться и заканчиваться на разных остановках.
Условия:
Каждый маршрут должен быть простым путем, то есть не содержать циклов.
Все маршруты должны быть попарно непересекающимися по рёбрам дорог (одна дорога не может быть частью двух разных маршрутов).
Общая длина всех маршрутов должна быть минимальной.
Если построить K маршрутов невозможно, необходимо вывести сообщение об этом.
Формат входных данных
В первой строке даны два целых числа N и M (2 ≤ N ≤ 2·10^5, 1 ≤ M ≤ 3·10^5) — количество остановок и дорог.
В следующих M строках описаны дороги: три целых числа u v w (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w ≤ 10^9) — дорога между остановками u и v длиной w километров.
В следующей строке дано целое число K (1 ≤ K ≤ 10^5) — количество маршрутов.
В следующих K строках описаны маршруты, которые нужно построить: два числа s t — начальная и конечная остановки маршрута.
Формат выходных данных
Если построить маршруты невозможно, вывести -1.
Иначе в первой строке вывести одно число — минимальную возможную суммарную длину всех маршрутов.
Далее для каждого маршрута в отдельной строке вывести сам путь в формате:
сначала число L — количество остановок на пути,
затем L чисел — номера остановок в порядке следования.
Пока нет ставок.
