Условие

---

ГРУПА А. ЗАДАЧА D. ТРАНСПОРТНА НЕВОЛЯ
---
Ето, случи се! Мими покани най-сетне Гошко на среща! Разбира се, нещата не са никак лесни. Мими живее далеч, Бургас е голям, а Гошо трябва да се пребори да достигне до нея (физически и до сърцето ѝ, разбира се)! За тази цел той трябва да се пребори и с транспортна задача!

В град Бургас има n на брой спирки. Те са свързани с m на брой автобусни маршрути, като път от спирка ai до bi се изминава за време ti. За да стигне бързо и безопасно до Мими, Гошко може да смени най-много k автобуса. Понеже Гошо е много залухан, може да се окаже, че има нужда да знае най-краткото време за достигне между различните спирки, според своите нужди. Ще получите от него q на брой запитвания, като на всяко от тях трябва да върнете най-краткото време за достигне от едната до другата спирка. Ако няма такава възможност, отговорете с -1.

Вход:
Първия ред съдържа две цели числа n (1 < n < 70) и m (1 < m < 106), разделени с интервал. На всеки от следващите m реда са разположени по три цели числа във формат: ai bi ti (1 < ai, bi < n, 1 < ti < 106). На следващия ред са разопложени две цели числа k и q (1 <= k <= 109, 1 <= q <= n2), максималния брой сменени автобуси и брой на заявките. На следващите q реда са разположени по две цели числа във формата: cj dj, които са началната и крайната позиция, за която се пита.

Изход:
Изведете q на брой реда, като на всеки от редовете изведете полученото минимално време за съответната заявка.

Примерeн вход:
4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
1 3
1 4
4 2
3 3	

Примерен изход:
10
-1
0